Pagini recente » Cod sursa (job #295635) | Cod sursa (job #2803756) | Cod sursa (job #2289192) | Cod sursa (job #1656166) | Cod sursa (job #3344951)
#include <iostream>
#define NMAX 2000005
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();
for (int i = 1, j = 0; i < m && j < m - 1; ++i) {
if (p[i] == p[j]) {
dfa[i] = j + 1;
++j;
} else {
dfa[i] = 0;
j = 0;
}
}
for (int i = 0, j = 0; i < n && cnt < 1000; ++i) {
if (t[i] != p[j] )
if (j > 0)
j = dfa[j - 1];
if (t[i] == p[j] && j == m - 1) {
pos[cnt++] = i - m + 1;
if (j > 0)
j = dfa[j - 1];
}
if (t[i] == p[j] && j < m - 1)
++j;
}
std::cout << cnt << '\n';
for (int i = 0; i < cnt; ++i)
std::cout << pos[i] << ' ';
std::cout << '\n';
return 0;
}