Pagini recente » Cod sursa (job #1834190) | Istoria paginii runda/luca_oji2 | Cod sursa (job #990721) | Cod sursa (job #1175962) | Cod sursa (job #167288)
Cod sursa(job #167288)
#include <stdio.h>
#include <string.h>
#define nmax 2000005
#define MOD 17
#define base 27
int N, M, H0, base2, H[nmax], pot, V[1024];
char T[nmax], P[nmax];
void read()
{
freopen("strmatch.in", "r", stdin);
scanf("%s\n%s", &P, &T);
}
void solve()
{
int i, j, k;
N = strlen(T);
M = strlen(P);
for (i = 0; i < M; ++i)
H0 = (H0 * base + P[i]-'A') % MOD;
for (i = 0; i < M; ++i)
H[M-1] = (H[M-1] * base + T[i]-'A') % MOD;
for (base2 = 1, i = 1; i <= M; ++i)
base2 *= base;
for (i = M; i < N; ++i)
H[i] = (H[i-1]%MOD * base + T[i]-'A' - base2%MOD*(T[i-M]-'A')%MOD + MOD) % MOD;
for (i = M-1; i < N; ++i)
if (H[i] == H0)
{
for (j = 0, k = i-M+1; j < M && P[j] == T[k]; ++k, ++j);
if (j == M)
{
if (pot < 1000)
{
V[++pot] = k-M;
}
}
}
}
void write()
{
int i;
freopen("strmatch.out", "w", stdout);
printf("%d\n", pot);
for (i = 1; i <= pot; ++i)
printf("%d ", V[i]);
}
int main()
{
read();
solve();
write();
return 0;
}