Pagini recente » Cod sursa (job #2407855) | Cod sursa (job #579834) | Cod sursa (job #931344) | Cod sursa (job #2904282) | Cod sursa (job #3157481)
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> KMP(string &srch,string &pat)
{
vector<ll> lps(pat.size());
ll i,j;
for(i=1;i<pat.size();i++)
{
j=i;
do
{
j=lps[j-1];
}while(j!=0&&pat[i]!=pat[j]);
lps[i]=j+(pat[i]==pat[j]);
}
vector<ll> rez;
j=0;
for(i=0;i<srch.size();i++)
{
while(j&&pat[j]!=srch[i])j=lps[j-1];
if(pat[j]==srch[i])j++;
if(j==pat.size())rez.emplace_back(i-pat.size()+1),j=lps[j-1];
}
return rez;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
string a,b;
cin>>a>>b;
vector<ll> rez=KMP(b,a);
cout<<rez.size()<<'\n';
for(ll i=0;i<rez.size()&&i<1000;i++)cout<<rez[i]<<' ';
return 0;
}