Cod sursa(job #1198642)

Utilizator usermeBogdan Cretu userme Data 16 iunie 2014 15:23:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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,sizeof(b),f);
    while( c!='\n' ){
        c=b[++n];
    }
    --n;
    fgets(a+1,sizeof(a),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;
}