Pagini recente » Cod sursa (job #2049864) | Cod sursa (job #71240) | Cod sursa (job #1797714) | Cod sursa (job #1746952) | Cod sursa (job #1305979)
//KMP
#include <fstream>
#include <string>
#include <vector>
int main(){
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string P,T; fin>>P>>T;
unsigned m=P.size();
unsigned n=T.size();
//compute the table
std::vector<unsigned> prefix(m);
prefix[0]=0;
unsigned k=0;
for(unsigned i=1;i<m;++i){
while(k>0&&P[i]!=P[k]) k=prefix[k-1];
if(P[i]==P[k]) ++k;
prefix[i]=k;
}
unsigned nr=0;
unsigned matches[1000];
//check the string
unsigned q=0; //number of characters matched
for(unsigned i=0;i<n;++i){
while(q>0&&P[q]!=T[i]) q=prefix[q];
if(P[q]==T[i]) ++q;
if(q==m){
if(nr<1000){ matches[nr]=i+1-m; }
++nr;
q=prefix[q-1];
}
}
fout<<nr<<'\n';
unsigned nrm=1000;
if(nr<1000) nrm=nr;
for(unsigned i=0;i<nrm;++i) fout<<matches[i]<<' ';
fout<<'\n';
}