Pagini recente » Cod sursa (job #1619155) | Cod sursa (job #1254449) | Cod sursa (job #2060895) | Cod sursa (job #2900656) | Cod sursa (job #3321467)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector<int> lps;
void compute_lps(string pat){
lps.resize(pat.size(),0);
int n=pat.size(),i=1,len=0;
while(i<n){
if(pat[len]==pat[i]){
len++;
lps[i]=len;
i++;
}
else{
if(len!=0){
len=lps[len-1];
}
else{
i++;
}
}
}
}
int main(){
int i,j,lenp,lent,nr;
string pat,text;
cin>>pat;
cin>>text;
compute_lps(pat);
vector<int> vres;
lenp = pat.size();
lent = text.size();
i=0;
j=0;
while(i<lent){
if(text[i]==pat[j]){
j++;
if(j==lenp){
vres.push_back(i-lenp+1);
j=lps[j-1];
}
i++;
}
else {
if(j>0){
j = lps[j-1];
}
else{
i++;
}
}
}
cout<<vres.size()<<"\n";
if(vres.size()>1000)
vres.resize(1000);
for(auto i:vres){
cout<<i<<" ";
}
return 0;
}