Pagini recente » Cod sursa (job #465540) | Cod sursa (job #597941) | Diferente pentru home intre reviziile 469 si 468 | Cod sursa (job #731025) | Cod sursa (job #163056)
Cod sursa(job #163056)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define pb push_back
#define sz(c) int((c).size())
#define MAXN 2000005
int N, M;
char A[MAXN], B[MAXN];
int Pref[MAXN];
vector<int> ret;
inline int min(int a, int b) { return (a < b ? a : b); }
void Prefix() {
int p = 0;
Pref[1] = 0;
for (int i = 2; i <= N; ++i) {
while (p && A[p+1] != A[i])
p = Pref[p];
if (A[p+1] == A[i])
++p;
Pref[i] = p;
}
}
void Matches() {
int p = 0;
for (int i = 1; i <= M; ++i) {
while (p && B[i] != A[p+1])
p = Pref[p];
if (A[p+1] == B[i])
++p;
if (p == N) {
ret.pb(i-N);
p = Pref[p];
}
}
}
void ReadData() {
scanf("%s", A+1);
scanf("%s", B+1);
N = strlen(A+1);
M = strlen(B+1);
}
void WriteData() {
printf("%d\n", sz(ret));
for (int i = 0; i < min(sz(ret), 1000); ++i)
printf("%d ", ret[i]);
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ReadData();
Prefix();
Matches();
WriteData();
}