Pagini recente » Cod sursa (job #2361639) | Cod sursa (job #2361839) | Cod sursa (job #2959667) | Cod sursa (job #1348174) | Cod sursa (job #3345011)
#include <iostream>
#define NMAX 200005
int main()
{
int n, m, cnt = 0;
std::string t, p;
int dfa[NMAX];
int pos[NMAX];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::cin >> p >> t;
m = p.length();
n = t.length();
dfa[0] = 0;
for (int i = 1, j = 0; i < m;) {
if (p[i] == p[j]) {
dfa[i] = j + 1;
++i;
++j;
} else {
if (j == 0) {
dfa[i] = 0; // -1 + 1
++i;
} else {
j = dfa[j - 1];
}
}
}
for (int i = 0, j = 0; i < n && cnt < 1000;) {
if (t[i] == p[j]) {
++i;
++j;
if (j == m) {
pos[cnt++] = i - m;
j = dfa[j - 1];
}
} else {
if (j == 0)
++i;
else
j = dfa[j - 1];
}
}
std::cout << cnt << '\n';
for (int i = 0; i < cnt; ++i)
std::cout << pos[i] << ' ';
std::cout << '\n';
return 0;
}