Cod sursa(job #166931)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 28 martie 2008 17:46:53
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#define maxim 2000010

long n,m,i,k;
long p[maxim+3],sol[maxim+3];
char a[maxim+3],b[maxim+3];

void pi()
 {
        k=0;
        for (i=2; i<=n; i++)
        {
                while (k && a[i]!=a[k+1])
                        k=p[k];
                if (a[k+1]==a[i]) { k++; }
                p[i]=k;
        }
 }

void kmp()
 {
        n=strlen(a+1)-1;
        m=strlen(b+1)-1;
        pi(); sol[0]=0; k=0; i=0;
        for (i=1; i<=m; i++)
        {
                while (k && b[i]!=a[k+1])
                	k=p[k];
                if (b[i]==a[k+1]) {k++;}
                if (k==n) { sol[0]++; sol[sol[0]]=i-n; k=p[k]; }
        }
 }

int main(void)
 {
        freopen("strmatch.in", "r", stdin);
        freopen("strmatch.out", "w", stdout);
        fgets(a+1, maxim, stdin);
        fgets(b+1, maxim, stdin);
        kmp();
        printf("%ld\n",sol[0]);
        if (sol[0]>1000) { sol[0]=1000; }
        for (i=1; i<=sol[0] ;i++) { printf("%ld ", sol[i]); }
        fclose(stdin); fclose(stdout);
        return 0;
 }