Cod sursa(job #3325041)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 24 noiembrie 2025 16:05:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/extc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string a, b;
    cin >> a >> b;
    string s = a + "#" + b;
    vector<int> kmp(s.size() + 1, 0);
    kmp[1] = 0;
    for (int i = 2; i <= s.size(); ++i) {
        int l = kmp[i - 1];
        while (l > 0 && s[l] != s[i - 1]) {
            l = kmp[l];
        }
        if (s[l] == s[i - 1]) {
            kmp[i] = l + 1;
        }
    }
    vector<int> v;
    for (int i = 1; i <= s.size(); ++i) {
        if (kmp[i] == a.size()) {
            v.push_back(i - 2 * a.size() - 1);
        }
    }
    cout << v.size() << "\n";
    for (int i = 0; i < min(1000, (int) v.size()); ++i) cout << v[i] << " ";
    cout << "\n";
    return 0;
}