Cod sursa(job #2565843)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 martie 2020 17:11:20
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

#define MAXN    2000005

#define FILENAME    std::string("strmatch")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int N, M;
char A[MAXN], B[MAXN];
int count;
std::vector <int> sol;
void addToSol(int idx) {
    ++ count;
    if (sol.size() < 1000) sol.push_back(idx);
}

int LPS[MAXN];
void computeLPS(char S[], int N) {
    int len = 0;
    for (int i=1; i<=N; ++i) {
        while (len != 0 && S[len+1] != S[i])
            len = LPS[len];
        LPS[i] = len;
        if (S[len+1] == S[i]) ++ len;
    }
}
void KMP() {
    computeLPS(A, N);
    int len = 0;
    for (int i=1; i<=M; ++i) {
        while (len != 0 && A[len+1] != B[i])
            len = LPS[len];
        if (A[len+1] == B[i]) ++ len;
        if (len == N) addToSol(i-len);
    }
}

int main()
{
    input >> (A+1) >> (B+1);
    N = strlen(A+1);
    M = strlen(B+1);
    KMP();
    output << count << '\n';
    for (auto &it:sol) output << it << ' ';

    return 0;
}