Pagini recente » Cod sursa (job #245855) | Cod sursa (job #1286669) | Cod sursa (job #2048138) | Cod sursa (job #392871) | Cod sursa (job #444825)
Cod sursa(job #444825)
#include <cstdio>
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
#define MAX 2000005
#define MAXM 1000
#define isChar(a) (('a'<=(a)&&(a)<='z')||('A'<=(a)&&(a)<='Z')||'0'<=(a)&&(a)<='9')
#define min(a,b) (((a)<(b))?(a):(b))
char A[MAX],B[MAX];
int pi[MAX],n=1,m=1,match[MAXM],nrm=0;
void build_prefix(){
pi[1]=0;
for(int q=2,k=0;q<=m;q++){
while(k && A[k+1]!=A[q])
k = pi[k];
if(A[k+1]==A[q])
k++;
pi[q]=k;
}
}
void kmp(){
for(int i=1,q=0;i<=n;i++){
while(q && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
q++;
if(q==m){
nrm++;
if(nrm<=MAXM){
match[nrm-1]=i-m;
}
q=pi[q];
}
}
}
int main(){
A[0]=B[0]=' ';
fgets(A+1,MAX,fin);
fgets(B+1,MAX,fin);
while(isChar(A[m]))m++;
while(isChar(B[n]))n++;
n--,m--;
build_prefix();
kmp();
fprintf(fout,"%d\n",nrm);
for(int i=0;i<min(nrm,MAXM);i++){
fprintf(fout,"%d ",match[i]);
}
fclose(fin);
fclose(fout);
return 0;
}