Pagini recente » Cod sursa (job #2868961) | Cod sursa (job #332182) | Cod sursa (job #1363697) | Cod sursa (job #448410) | Cod sursa (job #3291295)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int lps[2000003];
vector<int> rez;
int main()
{
fin>>a>>b;
int n=b.size(),m=a.size();
int st=0,dr=1;
while (dr<m)
{
if (a[dr]==a[st])
{
st++;
lps[dr]=st;
dr++;
}
else
{
if (st!=0) st=lps[st-1];
else dr++;
}
}
st=0,dr=0;
while (dr<n)
{
if (b[dr]==a[st])
{
dr++;
st++;
}
else
{
if (st!=0) st=lps[st-1];
else dr++;
}
if (st==m) rez.push_back(dr-m),st=lps[st-1];
}
fout<<rez.size()<<'\n';
for (auto i:rez)
fout<<i<<" ";
return 0;
}