Pagini recente » Cod sursa (job #471745) | Cod sursa (job #1234678) | Cod sursa (job #2482465) | Cod sursa (job #2718048) | Cod sursa (job #3151898)
/// Knuth - Morris - Pratt
#include <bits/stdc++.h>
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2")
#define ll long long
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define sz size()
#define all(x) (x).begin() + 1, (x).end()
#define allrev(x) (x).rbegin(), (x).rend() - 1
#define all0(x) (x).begin(), (x).end()
#define allrev0(x) (x).rbegin(), (x).rend()
using namespace std;
void solve()
{
string text, pattern;
cin >> pattern >> text;
ll n = text.sz;
ll m = pattern.sz;
vector<ll> pf(m);
pf[0] = 0;
for (ll i = 1, j = 0; i < m; i++)
{
while (pattern[i] != pattern[j] && j > 0)
j = pf[j - 1];
if (pattern[i] == pattern[j])
pf[i] = ++j;
else
pf[i] = 0;
}
vector<ll> ans;
for (ll i = 0, j = 0; i < n; i++)
{
while (text[i] != pattern[j] && j > 0)
j = pf[j - 1];
if (text[i] == pattern[j])
++j;
if (j == m)
{
j = pf[j - 1];
ans.pb(i - m + 1);
}
}
cout << ans.size() << '\n';
for (ll z : ans)
cout << z << ' ';
}
int main(void)
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios :: sync_with_stdio(false);
cin.tie(nullptr);
///ll tt; cin >> tt; while(tt--)
solve();
return 0;
}