Pagini recente » Cod sursa (job #1589915) | Cod sursa (job #2762045) | Cod sursa (job #719947) | Cod sursa (job #331512) | Cod sursa (job #1439780)
//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");
//long tot = 2000005;
char n[2000005], m[2000005];
long pi[200005], poz[1010], cur = 0;*/
fgets(n, 2000005, fi);
fgets(m, 2000005, fi);
long sn = (long)strlen(n), sm = (long)strlen(m), q = -1, k = -1;
pi[0] = -1;
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;
}