Pagini recente » Cod sursa (job #1294644) | Cod sursa (job #2768627) | Cod sursa (job #2280872) | Cod sursa (job #2799731) | Cod sursa (job #681546)
Cod sursa(job #681546)
#include <stdio.h>
#define N_MAX 2000010
char A[N_MAX], B[N_MAX];
int pi[N_MAX];
int sol[1005];
int n;
void precalc() {
pi[1] = 0;
int k = 0;
for(int i = 2; A[i] != '\n' && A[i]; i++) {
while(k > 0 && A[k+1] != A[i]) {
k = pi[k];
}
if(A[k+1] == A[i]) {
k++;
}
pi[i] = k;
n = i;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(A+1, N_MAX, stdin);
fgets(B+1, N_MAX, stdin);
precalc();
int k = 0;
for(int i = 1; B[i] != '\n' && B[i]; i++) {
while(k > 0 && A[k+1] != B[i]) {
k = pi[k];
}
if(A[k+1] == B[i]) {
k++;
}
if(k == n) {
sol[0]++;
if(sol[0] <= 1000) {
sol[sol[0]] = i-n;
}
}
}
printf("%d\n", sol[0]);
for(int i = 1; i <= sol[0] && i <= 1000; i++) {
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}