Cod sursa(job #1412196)

Utilizator BaTDucKMocanu George BaTDucK Data 1 aprilie 2015 10:21:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<bits/stdc++.h>

#define Nmax 2000003

using namespace std;

char A[Nmax], B[Nmax];
int pi[Nmax], DIM, V[Nmax], N;

void Write()
{
    freopen("strmatch.out", "w", stdout);

    printf("%d\n", DIM);
    for(int i = 1; i <= min(DIM, 1000); ++ i)
        printf("%d ", V[i]);

}

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

    for(i = 1; A[i]; ++ i) {

        while(k && A[k] != A[i])
            k = pi[k - 1];

        if(A[k] == A[i])
            ++ k;

        pi[i] = k;
    }

    N = i;
}

void Do_KMP()
{
    int k = 0;

    for(int i = 0; B[i]; ++ i) {

        while(k && A[k] != B[i])
            k = pi[k - 1];

        if(A[k] == B[i])
            ++ k;

        if(k == N)
            V[++ DIM] = i - N + 1;
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    gets(A);
    gets(B);

    prefix();
    Do_KMP();

    Write();
    return 0;
}