Cod sursa(job #2339638)

Utilizator tomadimitrieDimitrie-Toma Furdui tomadimitrie Data 9 februarie 2019 10:52:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

int main() {
    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");
    char s[2000001], t[2000001];
    fin >> (s + 1) >> (t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    int ap = 0;
    // calculam p[i] - lungimea maxima a unui sufix terminat la pozitia care totodata este prefix al lui s
    int p[2000001];
    p[1] = 0;
    int L = 0;
    int sol[1001];
    for (int i = 2; i <= n; ++i) {
        // calculam p[i]
        while (L != 0 && s[i] != s[L + 1]) {
            L = p[L];
        }
        if (s[i] == s[L + 1]) {
            L++;
        }
        p[i] = L;
    }
    L = 0;
    for (int i = 1; i <= m; ++i) {
        // voi testa potrivire a lui s in t care se termina la pozitia i
        // semnificatia lui L la pasul i - lungimea maxima a unui sufix din t terminat la pozitia i care totodata este prefix de lungime L in s
        while (L != 0 && t[i] != s[L + 1]) {
            L = p[L];
        }
        if (t[i] == s[L + 1]) {
            L++;
        }
        if (L == n) {
            // potrivire
            ap++;
            if (ap <= 1000) {
                sol[ap] = i - n;
            }
            L = p[L]; // urmatoarea potrivire se poate suprapune cu cea curenta si o cautam extinzand cel mai lung prefix al intregului sir s
        }
    }
    fout << ap << '\n';
    if (ap > 1000) {
        ap = 1000;
    }
    for (int i = 1; i <= ap; ++i) {
        fout << sol[i] << ' ';
    }
}