Pagini recente » Cod sursa (job #2725073) | Cod sursa (job #630761) | Cod sursa (job #583042) | Cod sursa (job #805249) | Cod sursa (job #477928)
Cod sursa(job #477928)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <string>
using namespace std;
#define NMAX 2000005
char needle[NMAX], haystack[NMAX];
int pi[NMAX];
int N, M;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(needle);
gets(haystack);
N = strlen(needle);
M = strlen(haystack);
// scanf("%s %s", &needle, &haystack);
int k = pi[0] = -1;
for (int i = 1; i < N; i++) {
while (k > -1 && needle[i] != needle[k+1])
k = pi[k];
if (needle[i] == needle[k+1]) ++k;
pi[i] = k;
}
k = -1;
vector<int> r;
for (int i = 0; i < M; i++) {
while (k > -1 && haystack[i] != needle[k+1])
k = pi[k];
if (haystack[i] == needle[k+1])
++k;
if (k+1 == N) {
r.push_back(i-N+1);
k = pi[k];
}
}
printf("%d\n", r.size());
for (vector<int> :: iterator it = r.begin(); it != r.end(); it++)
printf("%d ", *it);
printf("\n");
return 0;
}