Cod sursa(job #559777)

Utilizator laurionLaurentiu Ion laurion Data 18 martie 2011 03:16:27
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstring>
#include<fstream>
#include<cstdio>
char a[2000000+10],b[2000000+10];
int pi[2000000+10];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(a+1,2000000+5,stdin);
    //char tmp=fgetc(stdin);
    fgets(b+1,2000000+5,stdin);
    int n,m;

    n=strlen(a+1);
    m=strlen(b+1);
    a[n--]='\0';
    b[m--]='\0';

    pi[1]=0;
    int k=0;
    for(int i=2;i<=n;++i)
    {
        while(k>0 && a[i]!=a[k+1])
            k=pi[k];
        if(a[i]==a[k+1])
            ++k;
        pi[i]=k;
    }

    k=0;
    int nr=0;
    int pos[1001]={0};
    for(int i=2;i<=m;++i)
    {
        while(k>0 && a[k+1]!=b[i])
            k=pi[k];
        if(a[k+1]==b[i])
            ++k;
        if(k==n)
        {
            ++nr;
            if(pos[0]<1000)
            {
                pos[++pos[0]]=i-n;
            }
        }
    }

    fprintf(stdout,"%d\n",nr);

    for(int i=1;i<=pos[0];++i)
        fprintf(stdout,"%d ",pos[i]);

    return 0;
}