Pagini recente » Cod sursa (job #1520930) | Cod sursa (job #2297477) | Cod sursa (job #1514197) | Cod sursa (job #3214714) | Cod sursa (job #2141540)
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
vector<int> kmp(string &A, string &B) {
int N = A.size(), M = B.size();
vector<int> pi(N, -1), sol;
int k = -1, i = 0;
for (i = 1; i < N; i++) {
while (k != -1 && A[i] != A[k + 1]) {
k = pi[k];
}
if (A[i] == A[k + 1]) {
k++;
}
pi[i] = k;
}
k = -1;
for (i = 0; i < M; i++) {
while (k != -1 && B[i] != A[k + 1]) {
k = pi[k];
}
if (B[i] == A[k + 1]) {
k++;
}
if (k == N - 1) {
sol.push_back(i - N + 1);
}
}
return sol;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string A, B;
cin >> A >> B;
vector<int> sol = kmp(A, B);
cout << sol.size() << endl;
for (int i = 0; i < sol.size() && i < 1000; i++) {
cout << sol[i] << ' ';
}
return 0;
}