Pagini recente » Cod sursa (job #409483) | Cod sursa (job #2023528) | Cod sursa (job #606665) | Cod sursa (job #1292308) | Cod sursa (job #166128)
Cod sursa(job #166128)
#include <stdio.h>
#include <string.h>
#define nmax 2000008
char T[nmax], P[nmax];
int E[1005], pi[nmax];
int N, M, Q;
void read()
{
freopen("strmatch.in", "r", stdin);
scanf("%s\n", &P);
scanf("%s", &T);
}
void prefix()
{
int i, k;
for (i = 2, k = 0; i <= M; ++i)
{
k = pi[i-1];
while (k && P[k+1] != P[i])
k = pi[k];
if (P[k+1] == P[i])
++k;
pi[i] = k;
}
}
void kmp()
{
int i, k;
for (i = 1, k = 0; i <= N; ++i)
{
while (k && T[i] != P[k+1])
k = pi[k];
if (P[k+1] == T[i])
++k;
if (k == M)
{
k = pi[k];
++Q;
if (Q <= 1000)
E[Q] = i-M;
}
}
}
void solve()
{
int i;
N = strlen(T);
M = strlen(P);
for (i = N; i; i--)
T[i] = T[i-1];
for (i = M; i; i--)
P[i] = P[i-1];
T[0] = P[0] = ' ';
prefix();
kmp();
}
void write()
{
int i;
freopen("strmatch.out", "w", stdout);
printf("%d\n", Q);
Q = Q < N? Q: N;
for (i = 1; i <= Q; ++i)
printf("%d ", E[i]);
}
int main()
{
read();
solve();
write();
return 0;
}