Pagini recente » Cod sursa (job #1688917) | Cod sursa (job #1688490) | Cod sursa (job #2376710) | Cod sursa (job #1688898) | Cod sursa (job #3345137)
#include <iostream>
#define NMAX 2000005
#define CNTMAX 1005
int main()
{
int n, m, cnt = 0;
std::string t, p;
int delta[NMAX];
int pos[CNTMAX];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::cin >> p >> t;
m = p.length();
n = t.length();
delta[0] = 0;
for (int i = 1, j = 0; i < m;) {
if (p[i] == p[j]) {
delta[i] = j + 1;
++i;
++j;
} else {
if (j == 0) {
delta[i] = 0; // -1 + 1
++i;
} else {
j = delta[j - 1];
}
}
}
for (int i = 0, j = 0; i < n;) {
if (t[i] == p[j]) {
++i;
++j;
if (j == m) {
pos[cnt++] = i - m;
j = delta[j - 1];
}
} else {
if (j == 0)
++i;
else
j = delta[j - 1];
}
}
std::cout << cnt << '\n';
for (int i = 0; i < cnt && i < CNTMAX; ++i)
std::cout << pos[i] << ' ';
std::cout << '\n';
return 0;
}