Pagini recente » Cod sursa (job #846184) | Cod sursa (job #548202) | Cod sursa (job #995365) | Cod sursa (job #2613530) | Cod sursa (job #721313)
Cod sursa(job #721313)
#include <cstring>
#include <vector>
#include <fstream>
#define nmax 2000010
using namespace std;
int F[nmax];
char pattern[nmax];
char sir[nmax];
int main(){
ifstream fin("strmatch.in");
fin>>pattern;
fin>>sir;
int i,j;
int m=strlen(pattern);
int n=strlen(sir);
//construiesc functia de esec
F[0]=0;
F[1]=0;
for(i=2;i<=m;i++){
j=F[i-1];
while(1){
if(pattern[j]==pattern[i-1]){
F[i]=j+1;break;
}
if(j==0){
F[i]=0;
break;
}
j=F[j];
}
}
//afisez
/*for(i=0;i<=m;i++)
cout<<F[i]<<" ";
cout<<endl;*/
//KMP
i=0;
j=0;
vector <int> buffer;
while(1){
if(j==n)break;
if(sir[j]==pattern[i]){
i++;
j++;
if(i==m){
//cout<<j-m<<" ";
buffer.push_back(j-m);
}
}else if(i>0)i=F[i];
else j++;
}
ofstream fout("strmatch.out");
fout<<buffer.size()<<endl;
for(i=0;i<buffer.size();i++)
fout<<buffer[i]<<" ";
fout<<endl;
return 0;
}