Pagini recente » Cod sursa (job #1759736) | Cod sursa (job #331632) | Cod sursa (job #1312838) | Cod sursa (job #83449) | Cod sursa (job #1439775)
//005
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
FILE* fi = fopen("strmatch.in", "rt");
FILE* fo = fopen("strmatch.out", "wt");
char n[2000005], m[2000005];
long pi[200005], poz[1010], cur = 0;
fscanf(fi, "%s%s", n, m);
long sn = strlen(n), sm = strlen(m), q = -1, k = -1;
pi[0] = 0;
for (long i = 1; i < sn; i++) {
while (k >= 0 && n[k + 1] != n[i])
k = pi[k];
if (n[k + 1] == n[i])
k++;
pi[i] = k;
}
for (long i = 0; i < sm; i++) {
while (q >= 0 && n[q + 1] != m[i])
q = pi[q];
if (n[q + 1] == m[i])
q++;
if (q == sn - 1) {
if (cur <= 1000)
poz[cur] = i - sn + 1;
cur++;
}
}
long l = min((long)1000, cur);
fprintf(fo, "%ld", cur);
for (int i = 0; i < l; i++)
fprintf(fo, "%ld ", poz[i]);
return 0;
}