Pagini recente » Cod sursa (job #2746021) | Monitorul de evaluare | Cod sursa (job #2589175) | Cod sursa (job #1733162) | Cod sursa (job #2077369)
#include <cstdio>
#include <string.h>
const int MAXN = 2e6;
const int MAX_POS = 1e3;
char s[MAXN + 1], p[MAXN + 1];
int pi[MAXN + 1], ans[MAX_POS];
int main() {
int k, q, n, m;
FILE *f = fopen("strmatch.in", "r");
fscanf(f, "%s%s", s, p);
fclose(f);
k = pi[0] = 0;
n = strlen(s);
for (q = 1; q < n; ++q) {
while ((k > 0) && s[q] != s[k]) {
k = pi[k - 1];
}
if (s[q] == s[k]) {
++k;
}
pi[q] = k;
}
q = k = 0;
m = strlen(p);
for (int i = 0; i < m; ++i) {
while ((q > 0) && (s[q] != p[i])) {
q = pi[q - 1];
}
if (s[q] == p[i]) {
++q;
}
if (q == n) {
if (k < MAX_POS) {
ans[k++] = i - n + 1;
} else {
k++;
}
}
}
f = fopen("strmatch.out", "w");
fprintf(f, "%d\n", k);
k = k <= MAX_POS ? k : MAX_POS;
for (int i = 0; i < k; ++i) {
fprintf(f, "%d ", ans[i]);
}
fprintf(f, "\n");
fclose(f);
return 0;
}