Pagini recente » Cod sursa (job #1736197) | Cod sursa (job #507948) | Cod sursa (job #1159080) | Cod sursa (job #2181285) | Cod sursa (job #176189)
Cod sursa(job #176189)
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 2000010
long n, m, pi[MAX], i, k, nr, store[1000];
char A[MAX], B[MAX];
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;
}