Pagini recente » Cod sursa (job #3361015) | Cod sursa (job #3361001) | Cod sursa (job #3359194) | Cod sursa (job #2066684) | Cod sursa (job #3361018)
#include <bits/stdc++.h>
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string a, b;
std::cin >> a >> b;
std::vector<int>pi(a.size(), 0);
for (int i = 1; i < (int)a.size(); i++) {
int j = pi[i - 1];
while (j > 0 && a[i] != a[j]) {
j = pi[j - 1];
}
if (a[i] == a[j]) {
j++;
}
pi[i] = j;
}
int j = 0;
int cnt_ = 0;
std::vector<int>sol;
for (int i = 0; i < (int)b.size(); i++) {
while (j > 0 && b[i] != a[j]) {
j = pi[j - 1];
}
if (b[i] == a[j]) {
j++;
}
if (j == (int)a.size()) {
if (cnt_++ <= 1000) {
sol.push_back(i - (int)a.size());
}
j = pi[j - 1];
}
}
std::cout << sol.size() << '\n';
for (auto &c : sol)
{
std::cout << c + 1 << ' ';
}
}