Cod sursa(job #2152192)

Utilizator CammieCamelia Lazar Cammie Data 5 martie 2018 12:32:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <cstring>

#define MAXN 2000005

using namespace std;

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

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

vector <int> sol;

inline void Read() {
    fin >> (P + 1); N = strlen(P + 1);
    fin >> (T + 1); M = strlen(T + 1);
}

inline void Det_pi() {
    int k = 0;
    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() {
    int k = 0;

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

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

    for (auto x : sol) {
        fout << x << " ";
    }
}

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

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