Cod sursa(job #1249218)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 26 octombrie 2014 18:04:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>

#define Nmax (1 << 10)
#define Smax 2000100
#define root 0

using namespace std;

int N, nS, Fail[Smax], Solution[Nmax];
char A[Smax], B[Smax];

void Kmp() {

    int i, node;

    node = root;

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

        while(node != root && B[i] != A[node + 1])
            node = Fail[node];

        if(B[i] == A[node + 1])
            node++;

        if(node == N) {

            node = Fail[node];
            ++nS;

            if(nS <= 1000)
                Solution[nS] = i - N;

            }

        }

}
void Prefix() {

    int i, node;

    node = root;
    Fail[1] = root;

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

        while(node != root && A[i] != A[node + 1])
            node = Fail[node];

        if(A[i] == A[node + 1])
            node++;

        Fail[i] = node;

        }

    N = i - 1;

}
void Read() {

    ifstream in("strmatch.in");
    in.getline(A + 1, Smax);
    in.getline(B + 1, Smax);
    in.close();

}
void Write() {

    ofstream out("strmatch.out");
    out << nS << '\n';

    nS = min(nS, 1000);
    for(int i = 1; i <= nS; i++)
        out << Solution[i] << ' ';

    out << '\n';
    out.close();

}
int main() {

    Read();
    Prefix();
    Kmp();
    Write();

    return 0;

}