Cod sursa(job #2861451)

Utilizator Toaster_KeyboardMihaescu Vlad-Mihai Toaster_Keyboard Data 3 martie 2022 23:24:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
#define ll int int

// ======== Files ========
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#pragma endregion Template

vector<int> automata_prefix(string str) {
    int cnt = 0;
    vector<int> pi(int(str.size()));
    for (int i = 1; i < int(str.size()); i++) {
        while (cnt && str[cnt] != str[i])
            cnt = pi[cnt - 1];
        if (str[cnt] == str[i])
            ++cnt;
        pi[i] = cnt;
    }
    return pi;
}

vector<int> automataKMP(vector<int> patt, string pattStr, string str) {
    vector<int> positions;
    int cnt = 0;
    for (int i = 1; i < int(str.size()); i++) {
        while (cnt && pattStr[cnt] != str[i]) {
            cnt = patt[cnt - 1];
        }
        if (pattStr[cnt] == str[i])
            ++cnt;
        if (cnt == int(patt.size())) {
            positions.push_back(i - int(patt.size()) + 1);
        }
    }
    return positions;
}

void print(vector<int> toPrint) {
    cout << toPrint.size() << '\n';
    for (int i = 0; i < min(int(toPrint.size()), 1000); i++)
        cout << toPrint[i] << ' ';
}

void solve() {
    string pattern, text;
    cin >> pattern >> text;

    transform(pattern.begin(), pattern.end(), pattern.begin(), ::tolower);
    transform(text.begin(), text.end(), text.begin(), ::tolower);

    vector<int> prefixVector = automata_prefix(pattern);
    vector<int> ans = automataKMP(prefixVector, pattern, text);
    print(ans);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;  //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}