Pagini recente » Cod sursa (job #844539) | Cod sursa (job #2680518) | Rating Andrei (andrei2707) | Cod sursa (job #117980) | Cod sursa (job #164714)
Cod sursa(job #164714)
#include<fstream>
#include<string.h>
using namespace std;
int pf[2000001],n,m, r[1001], lim;
char a[2000001], b[2000001];
void KMP(){
int k,i;
k=0;
for(i=1;i<=n;i++){
while(k>0&&a[k]!=b[i-1])
k=pf[k];
if(a[k]==b[i-1])
k++;
if(k==m-1){
if(lim<1000) r[lim++]=i-m+1;
else lim++;
k=pf[k];
}
}
}
void prefix(){
int i, k;
pf[1]=0;
k=0;
for(i=2;i<=m;i++){
while( k>0 && a[k]!=a[i-1])
k=pf[k];
if(a[k]==a[i-1])
k++;
pf[i-1]=k;
}
}
int main(){
int i;
ifstream f("strmatch.in");
f>>a>>b;
f.close();
m=strlen(a);
n=strlen(b);
prefix();
KMP();
ofstream g("strmatch.out");
g<<lim<<'\n';
for(i=0;i<lim&&i<1000;i++)
g<<r[i]<<' ';
g<<'\n';
g.close();
return 0;
}