Pagini recente » Cod sursa (job #770226) | Cod sursa (job #1310222) | Cod sursa (job #944351) | Cod sursa (job #1375415) | Cod sursa (job #1716439)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;
int cnt;
int matches[1000];
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(cnt<1000) matches[cnt++]=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(int i=0;i<cnt;++i) fout<<matches[i]<<' ';
fout<<'\n';
}