Pagini recente » Cod sursa (job #2602039) | Cod sursa (job #1116332) | Cod sursa (job #1914555) | Cod sursa (job #2884388) | Cod sursa (job #1189955)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int maxl = 2000006;
char a[maxl],b[maxl];
int k,p[maxl];
int poz[1005];
int n,m,nr=0;
void kmp(char *a,int n,char *b,int m){
int i;
p[1]=0;
k=0;
for(i=2;i<=n;i++){
while(k>0 && a[k+1]!=a[i]) k=p[k];
if(a[k+1]==a[i]) k++;
p[i]=k;
}
k=0;
for(i=1;i<=m;i++){
while(k>0 && a[k+1]!=b[i]) k=p[k];
if(a[k+1]==b[i]) k++;
if(k==n){ nr++; if(nr<=1000) poz[nr]=i-n; }
}
}
void tipar(int nr){
int i;
fo<<nr<<"\n";
for(i=1;i<=nr;i++) fo<<poz[i]<<" ";
}
int main(){
fi>>(a+1); n=strlen(a+1);
fi>>(b+1); m=strlen(b+1);
kmp(a,n,b,m);
tipar(nr);
fi.close();
fo.close();
return 0;
}