Pagini recente » Cod sursa (job #2125637) | Cod sursa (job #971463) | Cod sursa (job #2174859) | Cod sursa (job #2940551) | Cod sursa (job #1439785)
//005
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>
#define li list<long>::iterator
using namespace std;
int main() {
FILE* fi = fopen("strmatch.in", "rt");
FILE* fo = fopen("strmatch.out", "wt");
char* n = (char*)malloc(2000001 * sizeof(char));
char* m = (char*)malloc(2000001 * sizeof(char));
fscanf(fi, "%s%s", n, m);
// printf("%s\n%s", n, m);
long sn = strlen(n), sm = strlen(m), q = -1, k = -1, l = 0;
long* pi = (long*)malloc(sn * sizeof(long));
list<long> ord;
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) {
l++;
if (l <= 1000)
ord.push_back(i - sn + 1);
}
}
fprintf(fo, "%ld\n", l);
for (li it = ord.begin(); it != ord.end(); it++)
fprintf(fo, "%ld", *it);
return 0;
}