Cod sursa(job #1332163)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 1 februarie 2015 19:39:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>

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

using namespace std;

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

void Kmp() {

    int i, p, top = 0;

    p = root;

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

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

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

        if(A[p + 1] == 0) {
            ++Solutions;
            if(top < 1000) {
                Solution[++top] = i - p;
            }
        }
    }

}
void Prefix() {

    int i, p;

    p = root;
    Fail[1] = root;

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

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

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

        Fail[i] = p;
    }

}
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 << Solutions << '\n';

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

    out << '\n';
    out.close();
}
int main() {

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

    return 0;
}