Pagini recente » Cod sursa (job #3172868) | Cod sursa (job #3204305) | Cod sursa (job #2006458) | Cod sursa (job #1324828) | Cod sursa (job #3291292)
#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()-1,m=a.size()-1;
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+1) rez.push_back(dr-m-1),st=lps[st-1];
}
fout<<rez.size()<<'\n';
for (auto i:rez)
fout<<i<<" ";
return 0;
}