Cod sursa(job #1198637)

Utilizator usermeBogdan Cretu userme Data 16 iunie 2014 15:09:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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;
    fscanf(f,"%c",&c);
    while( c!='\n' ){
        b[++n]=c;
        fscanf(f,"%c",&c);
    }
    fscanf(f,"%c",&c);
    while ( c!='\n' ){
        a[++m]=c;
        fscanf(f,"%c",&c);
    }
    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);
    for ( int i=1;i<=t;++i )
        fprintf(h,"%d ",rez[i]);
    return 0;
}