Cod sursa(job #251587)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 2 februarie 2009 22:51:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<string.h>

#define NN 2000004

int pi[NN], n, m, s[1002], nr;
char a[NN], b[NN];


void prefix(){
int i, q = 0;

     for (i = 2; i <= n; i++){

        while ((q>0) && a[q+1] != a[i]) q = pi[q];

        if (a[q+1] == a[i]) q++;

        pi[i] = q;
     }
}
void kmp(){
int q, i;

    prefix();

    q = 0;

    for (i = 1, q = 0; i <= m; i++){

        while ((q>0) && a[q+1] != b[i]) q = pi[q];

        if (a[q+1] == b[i]) q++;

        if (q == n){

            ++nr;

            if (nr <= 1000) s[nr] = i-n;

        }
    }


}


int main(){

int i;
    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);

    kmp();

    printf("%d\n", nr);
    if (nr > 1000) nr = 1000;

    for (i = 1; i <= nr; i++) printf("%d ", s[i]);
    printf("\n");

    return 0;
}