Cod sursa(job #166944)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 28 martie 2008 18:03:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <cstring>
#define maxim 20010

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

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(); nr=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) { nr++; sol[nr]=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", nr);
        if (nr>1000) { nr=1000; }
        for (i=1; i<=nr ;i++) { printf("%ld ", sol[i]); }
        fclose(stdin); fclose(stdout);
        return 0;
 }