Cod sursa(job #144364)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 15:09:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <string.h>
#define mx 1<<21
long i,h,n,m,p;
long pi[mx+4];
long v[1024];
char s1[mx+4],s2[mx+4];

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;
}