Cod sursa(job #2865294)

Utilizator CristianPavelCristian Pavel CristianPavel Data 8 martie 2022 18:13:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[2000001];
char s2[2000001];
int lps[2000001];
int v[2000001];
int nr=0;
void lps_(char s1[], int lps[])
{
    int i=1;
    int j=0;
    int l1=strlen(s1);
    lps[0]=0;
    while(i<l1)
    {
        if(s1[i]==s1[j])
        {
            j++;
            lps[i]=j;
            i++;
        }
        else{
            if(j==0){
                lps[i]=0;
                i++;
            }
            else j=lps[j-1];
        }
    }
}
void kmp(char s1[], char s2[])
{
    int i=0;
    int j=0;
    int l1=strlen(s1);
    int l2=strlen(s2);
    while(i<l2)
    {
        if(s2[i]==s1[j])
        {
            i++;
            j++;
        }
        if(j==l1){
            nr++;
            v[i-j]=1;
            j=lps[j-1];
        }
        else if(s2[i]!=s1[j]){
            if(j!=0) j=lps[j-1];
            else i++;
        }
    }
}
int main()
{
    cin.get(s1,2000001);
    cin.get();
    cin.get(s2,2000001);
    if(strlen(s1)>strlen(s2)){
        cout<<"0";
        return 0;
    }
    lps_(s1,lps);
    kmp(s1,s2);
    cout<<nr<<" "<<endl;
    nr=0;
    for(int i=0;i<=strlen(s2) && nr<1000;i++)
    {
        if(v[i]){
            cout<<i<<" ";
            nr++;
        }
    }
    cin.close();
    cout.close();
    return 0;

}