Pagini recente » Cod sursa (job #2217942) | Cod sursa (job #477152) | Cod sursa (job #422316) | Cod sursa (job #795815) | Cod sursa (job #1833360)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 2000050
using namespace std;
char a[MAXN], b[MAXN];
int pi[MAXN], n, m, rez;
vector<int> sol;
void prefix()
{
int k = 0;
for (int i = 2; i <= n; i++) {
while (k && a[i] != a[k+1])
k = pi[k];
if (a[i] == a[k+1])
k++;
pi[i] = k;
}
}
void solve()
{
int k = 0;
for (int i = 1; i <= m; i++) {
while (k && b[i] != a[k+1])
k = pi[k];
if (b[i] == a[k+1])
k++;
if (k == n) {
rez++;
if (rez <= 1000)
sol.push_back(i-n);
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a+1);
n = strlen(a+1);
gets(b+1);
m = strlen(b+1);
prefix();
solve();
printf("%d\n", rez);
for_each(sol.begin(), sol.end(), [](int x){ printf("%d ", x); });
return 0;
}