Pagini recente » Cod sursa (job #2046689) | Cod sursa (job #570077) | Cod sursa (job #484146) | Cod sursa (job #2872784) | Cod sursa (job #2863951)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
char a[N], b[N];
int lps[N];
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> (a + 1) >> (b + 1);
cin.close();
int n = strlen(a + 1), m = strlen(b + 1);
int j = 0;
for (int i = 2; i <= n; ++i) {
while (j > 0 && a[j + 1] != a[i])
j = lps[j];
if (a[j + 1] == a[i])
++j;
lps[i] = j;
}
vector<int> sol;
j = 0;
for (int i = 1; i <= m; ++i) {
while (j > 0 && a[j + 1] != b[i])
j = lps[j];
if (a[j + 1] == b[i])
++j;
if (j == n)
sol.push_back(i - n);
}
cout << sol.size() << "\n";
for (int i = 0; i < min((int)sol.size(), 1000); ++i)
cout << sol[i] << " ";
cout.close();
return 0;
}