Pagini recente » Cod sursa (job #420451) | Cod sursa (job #2358611) | Cod sursa (job #2587381) | Cod sursa (job #3246011) | Cod sursa (job #2194659)
#include <bits/stdc++.h>
#define Nmax 2000006
using namespace std;
char A[Nmax], B[Nmax];
int prefix[Nmax], k, n, m;
vector <int> solution;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout); //strmatch
cin.getline(A, Nmax);
cin.getline(B, Nmax);
n = strlen(A);
m = strlen(B);
if (n > m) return !(cout << 0);
for (int i = 1; i < n; i++) {
while (k && A[k] != A[i])
k = prefix[k - 1];
if (A[k] == A[i])
k++;
prefix[i] = k;
}
k = 0;
for (int i = 0; i < m; i++) {
while (k && A[k] != B[i])
k = prefix[k - 1];
if (A[k] == B[i])
k++;
if (k == n) {
if (solution.size() <= 1002)
solution.push_back(i - n + 1);
k = prefix[k - 1];
}
}
cout << min((int)(solution.size()), 1000) << "\n";
for (int i = 0; i < solution.size() && i < 1000; i++)
cout << solution[i] << " ";
}