Cod sursa(job #2738686)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 6 aprilie 2021 11:09:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
void DAU(const string &task = "") {
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
        freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PLEC() {
    exit(0);
}
const int N(5e6 + 5);
int lsp[N], cnt;
string s1, s2;
vector<int> res;
signed main() {
    DAU("strmatch");
    cin >> s1 >> s2;
	string s = s1 + '*' + s2;
	int n1 = s1.size(), n = s.size(), i = 1, j = 0;
	while (i < n) {
        if (s[i] == s[j])
            lsp[i++] = ++j;
        else {
            if (!j) ++i;
            else j = lsp[j-1];
        }
    }
	for (int i = 0; i < n; ++i)
		if (lsp[i] == n1) {
            ++cnt;
            if (cnt <= 1000)
                res.emplace_back(i - 2 * n1);
        }
	cout << cnt << '\n';
	for (const int& i : res)
		cout << i << ' ';
    PLEC();
}