Cod sursa(job #1169347)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 10 aprilie 2014 22:57:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<cstdio>
#include<cstring>
void read(),solve();
int i,lenA,lenB,k,q,nr,v[2000005],prefix[2000005];
char A[2000005],B[2000005];
int main()
{
    read();
    solve();
}
void read()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf(" %s",A+1);lenA=strlen(A+1);
    scanf(" %s",B+1);lenB=strlen(B+1);
}
void solve()
{
    for(i=2;i<=lenA;i++)
    {
        while(k && A[k+1]!=A[i])k=prefix[k];
        if(A[k+1]==A[i])k++;
        prefix[i]=k;
    }
    for(i=1;i<=lenB;i++)
    {
        while(q && A[q+1]!=B[i])q=prefix[q];
        if(A[q+1]==B[i])q++;
        if(q==lenA)
        {
            q=prefix[lenA];
            v[++nr]=i-lenA;
        }
    }
    printf("%d\n",nr);
    nr=nr<1001?nr:1000;
    for(i=1;i<=nr;i++)
        printf("%d ",v[i]);
}