Cod sursa(job #2122756)

Utilizator Victor_IonescuVictor Ionescu Victor_Ionescu Data 5 februarie 2018 14:22:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <cstring>

#define MAXN 2000006

using namespace std;

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

vector <int> sol;

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

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

    N = strlen(P + 1); M = strlen(T + 1);
}

inline void Det_pi() {
    int k = 0;

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

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

        pi[i] = k;
    }
}

inline void KMP() {
    k = 0;
    for (int i = 1; i <= M; i++) {
        while (k > 0 && P[k + 1] != T[i]) {
            k = pi[k];
        }

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

        if (k == N) {
            sol.push_back(i - N);

            if (sol.size() == 1000) {
                return;
            }
        }
    }
}

inline void Afisare() {
    fout << sol.size() << "\n";
    int l = sol.size();

    for (int i = 0; i < l; i++) {
        fout << sol[i] << " ";
    }
}

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

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