Pagini recente » Cod sursa (job #1012923) | Cod sursa (job #2378130) | Cod sursa (job #582299)
Cod sursa(job #582299)
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2000010;
int n, m, pi[N];
char p[N], t[N];
vector<int> rez;
void read() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(p + 1);
gets(t + 1);
}
void init() {
for (n = 1; p[n]; ++ n);
-- n;
for (m = 1; t[m]; ++ m);
-- m;
}
void calc_pi() {
int q = 0;
pi[1] = 0;
for (int i = 2; i <= n; ++ i) {
while(q && p[i] != p[q + 1])
q = pi[q];
if (p[i] == p[q + 1])
++ q;
pi[i] = q;
}
}
void solve() {
int q = 0;
for (int i = 1; i <= m; ++ i) {
while(q && t[i] != p[q + 1])
q = pi[q];
if (t[i] == p[q + 1])
++ q;
if (q == n) {
rez.push_back(i - n);
if (rez.size() == 1000)
break;
q = pi[q];
}
}
}
void afis() {
printf("%d\n", rez.size());
for (int i = 0; i < rez.size(); ++ i)
printf("%d ", rez[i]);
printf("\n");
}
int main() {
read();
init();
calc_pi();
solve();
afis();
return 0;
}