Cod sursa(job #1511890)

Utilizator nacrocRadu C nacroc Data 27 octombrie 2015 11:49:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <cstring>
#define NMAX 2000005

using namespace std;

char A[NMAX];//model
char B[NMAX];//sir
int L[NMAX], N, M, sol[NMAX];

void prefix(){
    int k;
    L[1] = 0;
    for(int p = 2; p <= N; p++){
        k = L[p-1];
        while(k > 0 && A[k] != A[p-1])
            k = L[k];
        if(A[k] == A[p-1])
            ++k;
        L[p] = k;
    }
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", A, B);
    N = strlen(A);//model
    M = strlen(B);//sir
    prefix();
    int k = 0, ind = 0;
    for(int t = 1; t <= M; ++t){
        while(k > 0 && A[k] != B[t-1])
            k = L[k];
        if(A[k] == B[t-1])
            ++k;
        if(k == N){
            sol[++ind] = t - N;
            k = L[k];
        }
    }
    printf("%d\n", ind);
    if(ind > 1000)
        ind = 1000;
    for(int i = 1; i <= ind; ++i)
        printf("%d ", sol[i]);
    return 0;
}