Pagini recente » Cod sursa (job #709365) | Cod sursa (job #2727539) | Cod sursa (job #1311606) | Cod sursa (job #3122618) | Cod sursa (job #2573120)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define input "strmatch.in"
#define output "strmatch.out"
const int lMax = 2000003;
using namespace std;
char a[lMax], b[lMax];
int lga, k, lgb, ans1;
int pi[lMax];
vector <int> ans2;
main()
{
ifstream cin(input);
ofstream cout(output);
cin >> a + 1 >> b + 1;
lga = strlen(a + 1);
lgb = strlen(b + 1);
k = 0;
pi[1] = 0;
for (int i = 2; i <= lga; ++i)
{
while (k && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] = a[i])
++k;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= lgb; ++i)
{
while (k && a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
++k;
if (k == lga)
{
++ans1;
if (ans2.size() < 1000)
ans2.emplace_back(i - lga);
}
}
cout << ans1 << "\n";
for (auto i : ans2)
cout << i << " ";
return 0;
}