Cod sursa(job #241428)

Utilizator firewizardLucian Dobre firewizard Data 10 ianuarie 2009 01:45:16
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>  
#include <string>  
char a[2000030],b[2000030];  
long v[2000030],vsol[2000030],i,j,k,l,n,m,q;  
int main()  
{  
    freopen ("strmatch.in","r",stdin);  
    freopen ("strmatch.out","w",stdout);  
    scanf("%s",a+1);n=strlen(a+1);  
    scanf("%s",b+1);m=strlen(b+1);  
    k=0;  
    for (i=2;i<=n;++i){  
        while (k>0&&a[k+1]!=a[i])  
              k=v[k];  
        if (a[k+1]==a[i])++k;  
        v[i]=k;  
        }     
    k=0;  
    for (i=1;i<=m;++i){  
        while(k>0&&a[k+1]!=b[i])k=v[k];  
        if(a[k+1]==b[i])k++;  
        if(k==n)vsol[++l]=i-n;  
        }  
    printf("%ld\n",l);  
    for(i=1;i<=l;++i)  
    printf("%ld ",vsol[i]);  
    return 0;  
}