Cod sursa(job #738567)

Utilizator Nicusor002Telechi Nicolae Nicusor002 Data 20 aprilie 2012 21:14:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<cstring>
#define dim 2000005
char a[dim],b[dim];
int n,m,sol[1005],contor,pref[dim];

void prefix(){
    int i,k;
    for(i=1;i<=n;i++){
        k=pref[i-1];
        while(k>0 && a[i]!=a[k]) k=pref[k-1];
        if(a[i]==a[k]){
            k++;
            pref[i]=k;
        }
    }
}

void kmp(){
    int i,k=0;
    for(i=0;i<=m;i++){
        while(k>0 && a[k]!=b[i]) k=pref[k-1];
        if(a[k]==b[i])
            k++;
        if(k==n+1){
            ++contor;
            if(contor<=1000)
                sol[contor]=i-k+1;
        }
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(a,dim,stdin);
    fgets(b,dim,stdin);
    n=strlen(a)-2; m=strlen(b)-2;
    prefix(); kmp();
    printf("%d\n",contor);
    for(int i=1;i<=(contor<1000?contor:1000);i++)
        printf("%d ",sol[i]);
}