Pagini recente » Cod sursa (job #2294989) | Cod sursa (job #2251543) | Cod sursa (job #249626) | Cod sursa (job #1356737) | Cod sursa (job #2019036)
#include <stdio.h>
#include <vector>
#include <cstdio>
#include <string.h>
using namespace std;
#define NMAX 2000000
int table[NMAX];
char A[NMAX], B[NMAX];
vector<int> solutions;
// void make_table(string A) {
// table[1] = 0;
// int j = 0, i = 0;
// len = strlen(A);
// while (i < len && j < len) {
// if (A[i] == A[j]) {
// table[i] = table[j] + 1;
// i++;
// j++;
// } else {
// j = table[j - 1];
// if (A[j] != A[i]) {
// table[i] = table[j];
// i++;
// }
// }
// }
// }
void make_prefix() {
int i;
int j = 0;
int M = strlen(A);
for (i = 1; i < M; i++) {
while (j && A[j] != A[i])
j = table[j];
if (A[j] == A[i])
j++;
table[i] = j;
}
}
void search() {
int i = 0, m = 0;
int N = strlen(B);
int M = strlen(A);
while(m + i < N) {
if (A[i] == B[m + i]) {
i++;
if (i == M) {
solutions.push_back(m);
m = m + i - table[i-1];
i = table[i-1];
}
} else {
if (i > 0) {
if (table[i-1] > 0) {
m = m + i - table[i-1];
i = table[i];
} else {
m = m + i + 1 - table[i-1];
i = 0;
}
} else {
m = m + i + 1;
i = 0;
}
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", A);
scanf("%s\n", B);
make_prefix();
search();
int s = solutions.size();
printf("%d\n", s);
int printed = 0;
for (std::vector<int>::iterator it = solutions.begin(); it != solutions.end() && printed < 1000; ++it) {
printf("%d ", *it);
printed++;
}
return 0;
}