Pagini recente » Cod sursa (job #3192171) | Cod sursa (job #2340304) | Cod sursa (job #230877) | Cod sursa (job #1815457) | Cod sursa (job #1497781)
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 2000010
using namespace std;
int kmp[MAXN], na, nb, solcnt;
char a[MAXN], b[MAXN];
vector<int> sol;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", a + 1, b + 1);
na = strlen(a + 1), nb = strlen(b + 1);
for(int i = 2; i <= na; i++) {
int x = kmp[i - 1];
while(x && a[x + 1] != a[i])
x = kmp[x];
if(a[x + 1] == a[i]) ++x;
kmp[i] = x;
}
int x = 0;
for(int i = 1; i <= nb; i++) {
while(x && a[x + 1] != b[i])
x = kmp[x];
if(a[x + 1] == b[i]) ++x;
if(x == na) {
++solcnt;
if(sol.size() < 1000) sol.push_back(i - na);;
x = kmp[x];
}
}
printf("%d\n", solcnt);
for(auto x: sol)
printf("%d ", x);
printf("\n");
return 0;
}