Cod sursa(job #2056540)

Utilizator CammieCamelia Lazar Cammie Data 4 noiembrie 2017 12:15:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>

#define MAXN 2000012

using namespace std;

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

char T[MAXN], P[MAXN];
int k, pi[MAXN], v[MAXN], nn, N, M, contor;

inline void Read() {
    fin >> (P + 1);

    fin >> (T + 1);
}

inline void Det_pi() {
    k = 0; pi[k] = 0;

    N = strlen(P + 1);

    for (int i = 2; i <= N; i++) {
        while (P[i] != P[k + 1] && k > 0) {
            k = pi[k];
        }

        if (P[i] == P[k + 1])
            k++;
        pi[i] = k;
    }
}

inline void KMP() {
    k = 0; M = strlen(T + 1);

    for (int i = 1; i <= M; i++) {
        while (k > 0 && T[i] != P[k + 1])
            k = pi[k];
        if (T[i] == P[k + 1])
            k++;
        if (k == N) {
            contor++;
            if (nn < 1000) {
                v[++nn] = i - N;
            }
            k = pi[k];
        }
    }
}

inline void Afisare() {
    fout << contor << "\n";

    for (int i = 1; i <= nn; i++) {
        fout << v[i] << " ";
    }
}

int main () {
    Read();
    Det_pi();
    KMP();
    Afisare();

    fin.close(); fout.close(); return 0;
}