Pagini recente » Cod sursa (job #3257104) | Cod sursa (job #1558289) | Cod sursa (job #1362677) | Cod sursa (job #2295411) | Cod sursa (job #493754)
Cod sursa(job #493754)
#include <stdio.h>
#include <string.h>
const long MAX = 2000010;
char A[MAX], B[MAX];
long n,m;
long pi[MAX],i,k;
long nr, Store[1000];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", A+1, B+1);
n = strlen(A + 1);
m = strlen(B + 1);
pi[1] = 0; k = 0;
for (i = 2; i <= n; ++i) {
while (k > 0 && A[i] != A[k + 1]) {
k = pi[k];
}
if (A[i] == A[k + 1]) {
++k;
}
pi[i] = k;
}
k = 0;
for (i = 1; i <= m; ++i) {
while (A[k + 1] != B[i] && k > 0) {
k = pi[k];
}
if (A[k + 1] == B[i]) {
++k;
}
if (k == n) {
++nr;
if (Store[0] < 1000) {
Store[++Store[0]] = i - n;
}
}
}
printf("%ld\n", nr);
for (i = 1; i <= Store[0]; ++i) {
printf("%ld ", Store[i]);
}
return 0;
}