Pagini recente » Cod sursa (job #1921883) | Cod sursa (job #108770) | Cod sursa (job #163019) | Cod sursa (job #276530) | Cod sursa (job #2063206)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
string p,txt;
int lp[1000];
vector <int> sol;
void patern()
{
int l=p.size();
int k=0;
for(int i=1;i<l;i++)
{
if(p[k]==p[i])
{
lp[i]=++k;
}
else
{
k--;
while(k>0)
{
k=lp[k];
if(p[k]==p[i])
{
lp[i]=++k;
break;
}
else
k--;
}
if(k<0)
k=0, lp[i]=0;
}
//cout<<lp[i]<<" ";
}
}
void solve()
{
int lt=txt.length();
int l=p.length();
int k=0, i=0;
while(i<lt)
{
if(txt[i]==p[k])
++k, ++i;
if(k==l)
{
if(sol.size()<1000)
sol.push_back(i-l), k=lp[k-1];
else
break;
}
else if(i<lt && p[k]!=txt[i])
{
if(k>0)
{
k=lp[k-1];
}
else
++i;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
getline(cin,p);
getline(cin,txt);
patern();
solve();
cout<<sol.size()<<"\n";
for(int i: sol)
cout<<i<<" ";
return 0;
}