Pagini recente » Cod sursa (job #1688941) | Cod sursa (job #1690809) | Cod sursa (job #3345140) | Cod sursa (job #3345138) | Cod sursa (job #3345221)
#include <cstring>
#include <iostream>
#define NMAX 2000005
#define KMAX 1000
int main()
{
int n, m, cnt = 0;
char t[NMAX], p[NMAX];
int delta[NMAX];
int pos[KMAX];
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::cin >> p >> t;
m = strlen(p);
n = strlen(t);
delta[0] = 0;
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && p[j] != p[i])
j = delta[j - 1];
if (p[j] == p[i])
++j;
delta[i] = j;
}
for (int i = 0, j = 0; i < n; ++i) {
while (j > 0 && p[j] != t[i])
j = delta[j - 1];
if (p[j] == t[i])
++j;
if (j == m) {
if (cnt < KMAX)
pos[cnt] = i - m + 1;
++cnt;
j = delta[j - 1];
}
}
std::cout << cnt << '\n';
for (int i = 0; i < cnt && i < KMAX; ++i)
std::cout << pos[i] << ' ';
std::cout << '\n';
return 0;
}