Pagini recente » Cod sursa (job #1734723) | Cod sursa (job #2333059) | Cod sursa (job #1538348) | Cod sursa (job #761184) | Cod sursa (job #1716434)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;
void build_pref(const string &s, vector<int> &pref){
pref[0]=0;
int q=0;
for(int i=1;i<s.size();++i){
while(q!=0 && s[i]!=s[q]) q=pref[q-1];
if(s[i]==s[q]) ++q;
pref[i]=q;
}
}
void kmp(const string &pat, const string &s, int &n, list<int> &lst){
n=0;
lst.clear();
vector<int> pref(pat.size());
build_pref(pat,pref);
int q=0;
//cout<<pat<<'\n';
//for(int i:pref) cout<<i;
//cout<<'\n';
for(int i=0;i<s.size();++i){
while(q!=0 && s[i]!=pat[q]) q=pref[q-1];
if(s[i]==pat[q]){
++q;
if(q==pat.size()){
++n;
if(lst.size()<1000) lst.push_back(i-pat.size()+1);
q=pref[q-1];
}
}
}
}
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pat,s;
fin>>pat>>s;
int n;
list<int> lst;
kmp(pat,s,n,lst);
fout<<n<<'\n';
for(auto i:lst) fout<<i<<' ';
fout<<'\n';
}