Cod sursa(job #1198641)

Utilizator usermeBogdan Cretu userme Data 16 iunie 2014 15:20:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>

FILE*f=fopen("strmatch.in","r");
FILE*h=fopen("strmatch.out","w");

int n,m,pref[2000001],k,rez[2000001],t;

char a[2000001],b[2000001];

int main(){
    char c=0;
    fgets(b+1,2000005,f);
    while( c!='\n' ){
        c=b[++n];
    }
    --n;
    fgets(a+1,2000005,f);
    c=0;
    while ( c!='\n' ){
        c=a[++m];
    }
    --m;
    pref[1]=0;
    for ( int i=2;i<=n;++i ){
        k=pref[i-1];
        while ( k>0&&b[k+1]!=b[i] )
            k=pref[k];
        if ( b[k+1]==b[i] )
            ++k;
        pref[i]=k;
    }
    k=0;
    for ( int i=1;i<=m;++i ){
        while ( k>0&&b[k+1]!=a[i] )
            k=pref[k];
        if ( b[k+1]==a[i] )
            ++k;
        if ( k==n ){
            rez[++t]=i-n;
            k=pref[k];
        }
    }
    fprintf(h,"%d\n",t);
    if ( t>1000 )t=1000;
    for ( int i=1;i<=t;++i )
        fprintf(h,"%d ",rez[i]);
    return 0;
}