Pagini recente » Cod sursa (job #525637) | Cod sursa (job #730766) | Cod sursa (job #1497580) | Cod sursa (job #635258) | Cod sursa (job #3321098)
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s,t;
vector <int> a;
int v[2000005],m,n,nr;
void rez(){
int l=0,i=1;
while(i<m){
if(s[l]==s[i])
++l,v[i]=l,++i;
else if(l)
l=v[l-1];
else
v[i]=0,++i;
}
}
void kmp(){
int l=0,i=0;
while(i<n){
if(t[i]==s[l]){
++l,++i;
if(l==m){
a.push_back(i-m);
l=v[l-1];
}
}
else if(l)
l=v[l-1];
else
++i;
}
}
signed main(){
cin>>s>>t;
m=s.size();
n=t.size();
rez();
kmp();
cout<<a.size()<<'\n';
a.resize(min((int)a.size(),1000));
for(auto i:a)
cout<<i<<' ';
}