Pagini recente » Istoria paginii utilizator/bobbychivescu | Monitorul de evaluare | Istoria paginii utilizator/andru_99 | Istoria paginii utilizator/dario2994 | Cod sursa (job #2014763)
#include <stdio.h>
#include <algorithm>
#include <string.h>
FILE *fin, *fout;
#define MAXDIM 2000000
int N, M;
char n[MAXDIM + 5], m[MAXDIM + 5];
int pi[MAXDIM + 5];
int ans[MAXDIM + 5];
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fgets(n + 1, MAXDIM + 3, fin);
fgets(m + 1, MAXDIM + 3, fin);
N = strlen(n + 1) - 1;
M = strlen(m + 1) - 1;///gaseste toate ap lui n in m
pi[1] = 0;
int k = 0;
for (int i = 2; i <= N; i++) {
while (k > 0 && n[i] != n[k + 1])
k = pi[k];
if (n[i] == n[k + 1])
k++;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= M; i++) {
while (k > 0 && m[i] != n[k + 1])
k = pi[k];
if (m[i] == n[k + 1]) {
k++;
}
if (k == N) {
if (ans[0] < 1000)
ans[++ans[0]] = i - N;
else
++ans[0];
}
}
fprintf(fout, "%d\n", ans[0]);
for (int i = 1; i <= std::min(1000, ans[0]); i++)
fprintf(fout, "%d ", ans[i]);
fclose(fin);
fclose(fout);
return 0;
}