Pagini recente » Cod sursa (job #1641934) | Cod sursa (job #2239975) | Cod sursa (job #1977422) | Cod sursa (job #2636416) | Cod sursa (job #148556)
Cod sursa(job #148556)
#include<stdio.h>
#include<string.h>
#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"
FILE *fin=fopen(INPUT,"r"),*fout=fopen(OUTPUT, "w");
char sir1[2000001],sir2[2000001];
int pref[2000001];
long vect[2001];
long cont;
void readValues();
void calculPrefix();
void KMP();
int main(){
cont=0;
readValues();
calculPrefix();
KMP();
fclose(fin);
fclose(fout);
return 0;
}
void readValues(){
char c;
long poz=0;
fscanf(fin, "%c", &c);
while(c!='\n'){
sir1[poz++]=c;
fscanf(fin, "%c", &c);
}
fscanf(fin, "%c", &c);
poz=0;
while(c!='\n' && !feof(fin)){
sir2[poz++]=c;
fscanf(fin, "%c", &c);
}
}
void calculPrefix(){
long N;
N=strlen(sir1);
long k=0;
pref[1]=0;
for(long i=1;i<N;++i){
while((k>0)&&(sir1[k]!=sir1[i]))
k=pref[k];
if(sir1[k]==sir1[i])
++k;
pref[i]=k;
}
}
void KMP(){
long N,M;
N=strlen(sir1);
M=strlen(sir2);
long q;
q=0;
for(long i=0;i<M;++i){
while(q>0 && sir1[q]!=sir2[i])
q=pref[q];
if(sir1[q]==sir2[i])
++q;
if(q==N){
if(cont<1000)
vect[++cont]=i-N+1;
}
}
fprintf(fout, "%ld\n", cont);
for(long i=1;i<=cont;++i)
fprintf(fout, "%ld ", vect[i]);
fprintf(fout, "\n");
}