Cod sursa(job #862836)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 22 ianuarie 2013 23:02:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb

#include <cstdio>
#include <cstring>
 
#define Nmax 2000005
 
int m, n;
char P[Nmax], T[Nmax];
int L[Nmax], V[Nmax];
int cont;
 
void citire(){
 
    freopen("strmatch.in", "r", stdin);
 
    fgets(P, sizeof(P), stdin);
    fgets(T, sizeof(T), stdin);
 
    m = strlen(P);
    n = strlen(T);
 
    for(int i = m; i > 0; i--)
        P[i] = P[i-1];
 
    for(int i = n; i > 0; i--)
        T[i] = T[i-1];
    n--;
    m--;
}
 
void prefix(){
 
    int k = 0;
 
    for(int i = 2; i <= m; ++i){
 
        while(k && P[k+1] != P[i])
            k = L[k];
 
        if(P[k+1] == P[i])
            k++;
 
        L[i] = k;
    }
}
 
void KMP(){
 
    int k = 0;
 
    for(int i = 1; i <= n; ++i){
 
        while(k && P[k+1] != T[i])
            k = L[k];
 
        if(P[k+1] == T[i])
            k++;
 
        if(k == m){
 
            k = L[m];
            V[++cont] = i-m;
        }
    }
}
 
void afis(){
 
    freopen("strmatch.out", "w", stdout);
 
    printf("%d\n", cont);
 
    for(int i = 1; i <= (cont < 1000 ? cont : 1000); i++)
        printf("%d ", V[i]);
 
    printf("\n");
}
 
int main(){
 
    citire();
    prefix();
    KMP();
    afis();
 
    return 0;
}