Pagini recente » Cod sursa (job #560744) | Cod sursa (job #3004706) | Profil florinhaja | Cod sursa (job #2083318) | Cod sursa (job #574448)
Cod sursa(job #574448)
#include<stdio.h>
#include<string.h>
#define dim 2000001
using namespace std;
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char x,m[dim],M[dim],i,y,v[1001],nr;
int p[2000001];
void prep(char m[],int x){
int k=0;
p[1]=0;
for(int i=2;i<=x;++i){
while(k>0&&m[k+1]!=m[i])
k=p[k];
if(m[k+1]==m[i])
++k;
p[i]=k;
}
}
void KMP(char M[],int x,int y){
int k=0;
for(int i=1;i<=y;++i){
while(k>0&&m[k+1]!=M[i])
k=p[k];
if(m[k+1]==M[i])
++k;
if(k==x)
if(nr<1000)
v[++nr]=i-x;
else ++nr;
}
}
inline int min(int a,int b){
if(a<b)
return a;
else return b;
}
int main() {
fscanf(f,"%s",m+1);
fscanf(f,"\n");
fscanf(f,"%s",M+1);
m[0]='a';
x=strlen(m)-1;
m[0]=0;
prep(m,x);
M[0]='a';
y=strlen(M)-1;
M[0]=0;
KMP(M,x,y);
fprintf(g,"%d\n",nr);
nr=min(nr,1000);
for(i=1;i<=nr;++i)
fprintf(g,"%d ",v[i]);
fclose(g);
fclose(f);
return 0;
}