Pagini recente » Cod sursa (job #2100207) | Cod sursa (job #3345123) | Cod sursa (job #2100670) | Cod sursa (job #2802639) | Cod sursa (job #3345126)
#include <iostream>
#define NMAX 2000005
int main() {
int n, m, cnt = 0;
std::string p, t;
int pi[NMAX];
int pos[1000];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::cin >> p >> t;
m = p.size();
n = t.size();
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && p[i] != p[j])
j = pi[j - 1];
if (p[i] == p[j])
++j;
pi[i] = j;
}
for (int i = 0, j = 0; i < n; ++i) {
while (j > 0 && t[i] != p[j])
j = pi[j - 1];
if (t[i] == p[j])
++j;
if (j == m) {
if (cnt < 1000)
pos[cnt++] = i - m + 1;
j = pi[j - 1];
}
}
std::cout << cnt << '\n';
for (int i = 0; i < cnt; ++i)
std::cout << pos[i] << ' ';
std::cout << '\n';
return 0;
}