Pagini recente » Cod sursa (job #1778700) | Cod sursa (job #2891894) | Cod sursa (job #1404628) | Cod sursa (job #1787428) | Cod sursa (job #2195312)
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
char A[Nmax], B[Nmax];
int a, b, prefix[Nmax];
vector <int> solution;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> B >> A;
a = strlen(A);
b = strlen(B);
int k = 0;
for (int i = 1; i < b; i++) {
while (k && B[k] != B[i])
k = prefix[k - 1];
if (B[k] == B[i])
k++;
prefix[i] = k;
}
k = 0;
for (int i = 0; i < a; i++) {
while (k && B[k] != A[i])
k = prefix[k - 1];
if (B[k] == A[i])
k++;
if (k == b)
k = prefix[k - 1],
solution.push_back(i - b + 1);
}
cout << solution.size() << "\n";
for (int i = 0; i < min(1000, (int)solution.size()); i++)
cout << solution[i] << " ";
}