Cod sursa(job #332143)

Utilizator freak93Adrian Budau freak93 Data 16 iulie 2009 20:10:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstring>
#include<cstdio>

using namespace std;

const int maxn=2000010;

char N[maxn],M[maxn];

int i,j,m,k,ras[1005],pi[maxn],q,n;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(N+1,sizeof(N),stdin);
    fgets(M+1,sizeof(M),stdin);
    q=0;
    pi[1]=0;
    for(i=2;N[i]!='\n'&&N[i]!=0;++i)
    {
        while(q&&N[q+1]!=N[i])
            q=pi[q];
        if(N[q+1]==N[i])
            ++q;
        pi[i]=q;
    }
    n=i-1;

    q=0;
    for(i=1;M[i]!='\n'&&M[i]!=0;++i)
    {
        while(q&&N[q+1]!=M[i])
            q=pi[q];
        if(N[q+1]==M[i])
            ++q;
        if(q==n)
        {
            q=pi[q];
            if(k<1000)
                ras[++k]=i-n;
        }
    }

    printf("%d\n",k);
    for(i=1;i<=k;++i)
        printf("%d ",ras[i]);
    printf("\n");

    fclose(stdin);
    fclose(stdout);

    return 0;
}