Pagini recente » Cod sursa (job #2027507) | Cod sursa (job #887772) | Cod sursa (job #2586740) | Cod sursa (job #1537826) | Cod sursa (job #3291297)
#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 cnt;
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)
{
cnt++;
if (rez.size()<1000) rez.push_back(dr-m);
st=lps[st-1];
}
}
fout<<cnt<<'\n';
for (auto i:rez)
fout<<i<<" ";
return 0;
}