Pagini recente » Cod sursa (job #2400724) | Cod sursa (job #2643476) | Cod sursa (job #2122938) | Cod sursa (job #760937) | Cod sursa (job #3151290)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int p[2000005];
int main()
{
in >> a;
in >> b;
int n = a.length();
int m = b.length();
int j = -1;
p[0] = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && a[i] != a[j + 1]) j = p[j];
if (a[i] == a[j + 1])
p[i] = j++;
p[i] = j;
}
j = -1;
vector<int> ans;
for (int i = 0; i < m; i++) {
while (j >= 0 && b[i] != a[j + 1]) j = p[j];
if (b[i] == a[j + 1]) {
j++;
if (j == n - 1) {
ans.push_back(i - n + 1);
j = p[j];
}
}
}
out << ans.size() << '\n';
int sz = ans.size();
for (int i = 0; i < min(sz, 1000); i++) {
out << ans[i] << " ";
}
return 0;
}