Cod sursa(job #1648132)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 11 martie 2016 01:43:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
# include <fstream>
# include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int L = 2000005;
typedef char sir[L];
sir X, Y;
int Pi[L], D[L];
int N, M, k, i, sol, nr;

int main() {
    fin >> (X+1) >> (Y+1);
    N = strlen(X+1);
    M = strlen(Y+1);

    k = 0;
    Pi[1] = 0;
    for (i=2; i<=N; ++i) {
        while (k > 0 && X[i] != X[k+1])
            k = Pi[k];

        if (X[i] == X[k+1])
            ++k;

        Pi[i] = k;
    }

    k = 0;
    for (i=1; i<=M; ++i) {
        while (k > 0 && Y[i] != X[k+1])
            k = Pi[k];

        if (Y[i] == X[k+1])
            ++k;

        D[i] = k;
        if (D[i] == N)
            ++sol;
    }

    fout << sol << "\n";
    for (i=1; i<=M; ++i) {
        if (D[i] == N) {
            --sol, ++nr;
            fout << i-N << " ";
        }

        if (sol == 0 || nr == 1000) break;
    }
    return 0;
}