Cod sursa(job #2803293)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 19 noiembrie 2021 19:15:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,nr,m;
int rez[2000005],urmator[2000005];
char s[2000005],pat[2000005];
void init()
{
    int i,j;
    urmator[1]=0;
    j=0;
    for(i=2; i<=n; i++)
    {
        while(j>0&&pat[i]!=pat[j+1])
            j=urmator[j];
        if(pat[i]==pat[j+1])j++;
        urmator[i]=j;
    }
}
;
void kmp()
{
    n=strlen(pat+1);
    m=strlen(s+1);
    init();
    urmator[0]=0;
    int i,j;
    int x;
    j=0;
    for(i=1; i<=m; i++)
    {
        while(s[i]!=pat[j+1]&&j>0)
            j=urmator[j];
        if(s[i]==pat[j+1])j++;
        if(j>=n){rez[++nr]=i-n;}
    }
    fout<<nr<<'\n';
    nr=min(nr,1000);
    for(i=1; i<=nr; i++)
    {
        fout<<rez[i]<<" ";
    }
}
int main()
{
    fin>>(pat+1);
    fin>>(s+1);
    kmp();
    return 0;
}