Mai intai trebuie sa te autentifici.
Cod sursa(job #349450)
Utilizator | Data | 19 septembrie 2009 17:02:49 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.06 kb |
#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]);
X = (X + P[i]);
}
for (i = 0; i < M; ++i)
{
V = (V + T[i]);
Y = (Y + T[i]);
}
if (U >= Q)
U %= Q;
if (V >= Q)
V %= Q;
if (X >= F)
Y %= F;
if (X >= F)
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];
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;
}