Pagini recente » Cod sursa (job #2661961) | Cod sursa (job #2522250) | Cod sursa (job #1912793) | Cod sursa (job #1338651) | Cod sursa (job #940826)
Cod sursa(job #940826)
#include <cstdio>
#include <cstring>
#define N_MAX (1<<21)
char P[N_MAX], T[N_MAX];
int Pi[N_MAX], Sol[N_MAX];
int N, M;
void Prefix_Function (char *P) {
M = strlen(P + 1) - 1;
int k = 0;
Pi[1] = 0;
for (int i = 2; i <= M; ++i) {
while (k > 0 && P[i] != P[k+1])
k = Pi[k];
if (P[i] == P[k + 1])
++k;
Pi[i] = k;
}
}
void KMP_String_Match (char *P, char *T) {
M = strlen(P + 1) - 1;
N = strlen(T + 1) - 1;
int k = 0;
for (int i = 1; i <= N; ++i) {
while (k > 0 && T[i] != P[k+1])
k = Pi[k];
if (T[i] == P[k+1])
++k;
if (k == M) {
Sol[++Sol[0]] = i - M;
k = Pi[k];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(P + 1, N_MAX, stdin);
fgets(T + 1, N_MAX, stdin);
Prefix_Function (P);
KMP_String_Match (P, T);
printf ("%d\n", Sol[0]);
for (int i = 1; i <= Sol[0]; ++i)
if (i <= 1000)
printf ("%d ", Sol[i]);
return 0;
}