Cod sursa(job #2909786)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 15 iunie 2022 19:22:13
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;
int T;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

vector<int> prefixKMP(const string &s) {
    vector<int> pr(s.size() + 1);
    pr[0] = -1;
    for (size_t i = 1; i <= s.size(); i++) {
        int k = pr[i - 1];
        while (k >= 0 && s[k] != s[i - 1]) {
            k = pr[k];
        }
        pr[i] = k + 1;
    }
    return pr;
}

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string A, B;
    fin >> A >> B;
    string concat = A + '#' + B;
    vector<int> pr = prefixKMP(concat);
    vector<int> ap;
    for (int i = (int) A.size() + 1; i < (int) concat.size(); i++) {
        if (pr[i] == A.size())
            ap.push_back(i - (int) A.size() * 2 - 1);
    }
    fout << ap.size() << '\n';
    for (int i = 0; i < min((int) ap.size(), 1000); i++)
        fout << ap[i] << ' ';
    return 0;
}