Cod sursa(job #855872)

Utilizator assa98Andrei Stanciu assa98 Data 15 ianuarie 2013 19:11:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <cstring>

char s1[2000200];
char s2[2000200];
int n,m;
int p[2000200];
int kmp;

void prefix()
{
    int x=0;
    for(int i=2;i<=m;i++)
    {
        while(x>0&&s1[x+1]!=s1[i])
            x=p[x];
        if(s1[x+1]==s1[i])
            x++;
        p[i]=x;
    }
}

int sol[1010];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    s1[0]=' ';
    s2[0]=' ';
    scanf("%s%s",s1+1,s2+1);
    m=strlen(s1);
    m--;
    n=strlen(s2);
    n--;
    prefix();
    kmp=0;
    for(int i=1;i<=n;i++)
    {
        while(kmp>0&&s1[kmp+1]!=s2[i])
            kmp=p[kmp];
        if(s1[kmp+1]==s2[i])
            kmp++;
        if(kmp==m)
        {
            kmp=p[m];
            sol[0]++;
            if(sol[0]<=1000)
                sol[sol[0]]=i-1;
        }
    }
    printf("%d\n",sol[0]);
    for(int i=1;i<=((sol[0]>1000)?1000:sol[0]);i++)
        printf("%d ",sol[i]);
    return 0;
}