Pagini recente » Cod sursa (job #1322670) | Cod sursa (job #1748374) | Cod sursa (job #1897532) | Cod sursa (job #1229113) | Cod sursa (job #1110314)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
char s1[NMAX], s2[NMAX];
int b[NMAX];
int n1, n2;
void preprocess() {
unsigned i;
int j = -1;
b[0] = -1;
for(i = 1; i <= n1; ++i) {
while(j >= 0 && s1[i-1] != s1[j])
j = b[j];
b[i] = ++j;
}
}
int sol[1001], all = 0;
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s", s1); scanf("%s", s2);
n1 = strlen(s1), n2 = strlen(s2);
preprocess();
unsigned i;
int j;
for(i = 0, j = 0; i < n2; ++i) {
while(j >= 0 && s1[j] != s2[i])
j = b[j];
++j;
if(j == n1) {
sol[all++] = i - n1 + 1;
if(all == 1000)
goto print;
j = b[j]; ++j;
}
}
print:
printf("%d\n", all);
for(i = 0; i < all; ++i)
printf("%d ", sol[i]);
return 0;
}