Pagini recente » Cod sursa (job #2176844) | Cod sursa (job #1856221) | Cod sursa (job #1808248) | Cod sursa (job #267519) | Cod sursa (job #169897)
Cod sursa(job #169897)
#include <stdio.h>
#include <string.h>
char S[2000100], W[2000100];
long T[2000100];
long i, j, m, ns, nw, nx, x[2000100];
int main()
{
freopen ("strmatch.in", "rt", stdin);
freopen ("strmatch.out", "wt", stdout);
scanf("%s\n%s", &W, &S);
ns = strlen(S);
nw = strlen(W);
i = 2;
j = 0;
T[1] = 0;
T[0] = -1;
while (i < nw)
{
if (W[i - 1] == W[j])
T[i] = j + 1, ++i, ++j;
else
if (j > 0)
j = T[j];
else
T[i] = 0, ++i;
}
m = i = 0;
while (m + i < ns)
{
if (W[i] == S[m + i])
{
++i;
if (i == nw)
{
x[++nx] = m;
//printf("%ld ", m);
i = T[i];
++m;
}
}
else
{
m = m + i - T[i];
if (i > 0)
i = T[i];
}
}
printf("%ld\n", nx);
nx = nx < 1000 ? nx : 1000;
for (i = 1; i <= nx; ++i)
printf("%ld ", x[i]);
printf("\n");
return 0;
}