Cod sursa(job #144779)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 22:43:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>   
#include <string.h>   
#define mx 2000010   
long i,h,n,m,p;   
long pi[mx+1];   
long v[1024];   
char s1[mx+2],s2[mx+2];   
  
void prefix()   
{   
        pi[0]=0;   
        p=0;   
        for (i=2; i<=n; i++)   
        {   
                while (p>0 && s1[i]!=s1[p+1])   
                        p=pi[p];   
                if (s1[i]==s1[p+1])   
                        p++;   
                pi[i]=p;   
        }   
}   
  
void kmp()   
{   
        n=strlen(s1+1)-1;   
        m=strlen(s2+1)-1;   
        prefix();   
        p=0;   
        h=0;   
        for (i=1; i<=m; i++)   
        {   
                while (p>0 && s2[i]!=s1[p+1])   
                        p=pi[p];   
                if (s2[i]==s1[p+1])   
                        p++;   
                if (p==n)   
                {   
                        h++;   
                        p=pi[p];   
                        if (h<=1000)   
                                v[h]=i-n;   
                }   
        }   
}   
  
int main(void)   
{   
        freopen("strmatch.in","r",stdin);   
        freopen("strmatch.out","w",stdout);   
        fgets(s1+1,mx,stdin);   
        fgets(s2+1,mx,stdin);   
        kmp();   
        printf("%ld\n",h);   
        if (h>1000)   
                h=1000;   
        for (i=1; i<=h; i++)   
                printf("%ld ",v[i]);   
        fclose(stdin);   
        fclose(stdout);   
        return 0;   
}