Pagini recente » Cod sursa (job #2662036) | Cod sursa (job #2210787) | Cod sursa (job #522300) | Cod sursa (job #1588457) | Cod sursa (job #249776)
Cod sursa(job #249776)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 2000015
int N, M;
char sir[MAXN], match[MAXN];
int p[MAXN];
vector <int> sol;
void read () {
fgets (match, MAXN, stdin);
fgets (sir, MAXN, stdin);
N = strlen(sir) - 1; M = strlen(match) - 1;
}
#define sir (sir - 1)
#define match (match - 1)
void prefix () {
int k = 0;
for (int i = 2; i <= M; ++ i) {
while (k > 0 && match[k + 1] != match[i]) k = p[k];
if (match[k + 1] == match[i]) ++ k;
p[i] = k;
}
}
void KMP () {
int k = 0;
for (int i = 1; i <= N; ++ i) {
while (k > 0 && match[k + 1] != sir[i]) k = p[k];
if (match[k + 1] == sir[i]) ++ k;
if (k == M) sol.push_back(i - M);
}
}
void solve () {
prefix ();
KMP ();
int sz = sol.size();
printf ("%d\n", sz);
for (int i = 0; i < sz; ++ i) printf ("%d ", sol[i]);
printf ("\n");
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w",stdout);
read ();
solve ();
return 0;
}