Pagini recente » Cod sursa (job #169403) | matrice_ | Cod sursa (job #2973957) | Cod sursa (job #3155889) | Cod sursa (job #1219995)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int last[2000010], nr;
vector<int> sol;
string a, b;
void pref() {
int k = 0;
last[1] = 0;
for (int i = 2; i < a.length(); i++) {
while (k > 0 && a[k+1] != a[i]) k = last[k];
if (a[k+1] == a[i]) k++;
last[i] = k;
}
}
void kmp() {
int k = 0;
for (int i = 1; i < b.length(); i++) {
while (k > 0 && a[k+1] != b[i]) k = last[k];
if (a[k+1] == b[i]) {
k++;
if (k == a.length() - 1) {
nr++;
if (nr <= 1000) {
sol.push_back(i - a.length() + 1);
}
k = last[k];
}
} else {
k = last[k];
}
}
}
int main() {
int x, y;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin >> a;
cin >> b;
a = " " + a;
b = " " + b;
pref();
kmp();
printf("%d\n", nr);
for (int i = 0; i < sol.size(); i++) {
printf("%d ", sol[i]);
}
return 0;
}