Pagini recente » Cod sursa (job #546187) | Cod sursa (job #2240904) | Cod sursa (job #796142) | Cod sursa (job #1062606) | Cod sursa (job #3278820)
#include <bits/stdc++.h>
using namespace std;
string s,a;
int lps[2000005];
vector <int> v;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>a>>s;
int i=1,j=0;
while(i<a.size())
{
while(j>0 && a[i]!=a[j])
{
j=lps[j-1];
}
if(a[i]==a[j])
{
++j;
}
lps[i]=j;
++i;
}
j=0;
for(int i=0;i<s.size();++i)
{
while(j>0 && s[i]!=a[j])
{
j=lps[j-1];
}
if(s[i]==a[j])
{
++j;
}
if(j==a.size())
{
v.push_back(i-a.size()+1);
j=lps[j-1];
}
}
cout<<v.size()<<"\n";
for(int i=0;i<v.size();++i)
{
cout<<v[i]<<" ";
}
return 0;
}