Pagini recente » Istoria paginii runda/ojisim/clasament | Rating stefanl (slayerb) | Cod sursa (job #217621) | Cod sursa (job #674106) | Cod sursa (job #349447)
Cod sursa(job #349447)
#include <stdio.h>
char P[2000002], T[2000002];
int U, V, Q, F, M, N, X, Y;
int R[1002];
int main()
{
int i, k, l;
Q = 666013;
F = 727777;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(P);
gets(T);
for (M = 0; P[M]; ++M);
for (N = 0; T[N]; ++N);
for (i = 0; i < M; ++i)
{
U = (U + P[i]) % Q;
X = (X + P[i]) % F;
}
for (i = 0; i < M; ++i)
{
V = (V + T[i]) % Q;
Y = (Y + T[i]) % F;
}
for (i = M-1; i < N; ++i)
{
if (V == U && X == Y)
{
for (k = 0, l = i-M+1; k < M; ++k, ++l)
if (P[k] != T[l])
break;
if (k == M)
{
++R[0];
if (R[0] <= 1000)
R[R[0]] = i-M+1;
}
}
V -= T[i-M+1];
V += T[i+1];
while (V < 0)
V += Q;
Y -= T[i-M+1];
Y += T[i+1];
while (Y < 0)
Y += F;
}
printf("%d\n", R[0]);
if (R[0] > 1000) R[0] = 1000;
for (i = 1; i <= R[0]; ++i)
printf("%d ", R[i]);
printf("\n");
return 0;
}