Pagini recente » Cod sursa (job #2649099) | Cod sursa (job #2741393) | Istoria paginii runda/ceau_oni2017_2/clasament | Cod sursa (job #1987894) | Cod sursa (job #349461)
Cod sursa(job #349461)
#include <stdio.h>
char P[2000002], T[2000002];
int U, V, Q, M, N, X, Y, F;
int R[1002];
int main()
{
int i, k, l;
Q = 666013;
F = 17;
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];
X = X + P[i];
}
U %= Q;
X %= F;
for (i = 0; i < M; ++i)
{
V = V + T[i];
Y = Y + T[i];
}
V %= Q;
Y %= 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];
if (V < 0)
V += Q;
else if (V >= Q)
V %= Q;
Y -= T[i-M+1];
Y += T[i+1];
if (Y < 0)
Y += F;
else if (Y >= F)
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;
}