Cod sursa(job #1552549)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 18 decembrie 2015 11:19:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <cstring>
using namespace std;
int phi[2000005],v[2000005],i,k,n,m,nr1;
char a[2000005],b[2000005];
int kmp(char a[2000005], char b[2000005],int n, int m, int v[2000005])
{
    a[n+2]=' ';
    phi[1]=0;
    for (i=2; i<=n; i++)
    {
        k=phi[i-1];
        while (a[i]!=a[k+1] && k>0) k=phi[k];
        if (a[i]==a[k+1]) phi[i]=k+1;
        else phi[i]=0;
    }
    for (i=1; i<=m; i++)
    {
        k=v[i-1];
        while (k>0 && b[i]!=a[k+1]) k=phi[k];
    if (b[i]==a[k+1]) v[i]=k+1;
    else v[i]=0;
    }
    int nr=0;
    for (i=1; i<=m; i++) if (v[i]==n) nr++;
    return nr;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    printf("%d\n",kmp(a,b,n,m,v));
    nr1=0;
    for (i=1; i<=m; i++) if (v[i]==n && nr1<1000) {printf("%d ",i-n); nr1++;}
    return 0;
}