Pagini recente » Cod sursa (job #1801217) | Cod sursa (job #2170114) | Cod sursa (job #1941263) | Cod sursa (job #2903334) | Cod sursa (job #416460)
Cod sursa(job #416460)
#include <stdio.h>
#define MAX 2000005
char A[MAX],B[MAX];
int pi[MAX],pos[1024],m,n,np=0;
void make_prefix(){
int i,q=0;
pi[1]=0;
for (i=2;i<=m;i++){
while(q&&A[q+1]!=A[i]){
q=pi[q];
}
if (A[q+1] == A[i]){
q++;
}
pi[i]=q;
}
}
int main(void)
{
int i, q = 0;
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
fgets(A, MAX, fin);
fgets(B, MAX, fin);
m=n=0;
while(('A'<=A[m]&&A[m]<='Z')||('a'<=A[m]&&A[m]<='z')||('0'<=A[m]&&A[m]<='9')){
m++;
}
while(('A'<=B[n]&&B[n]<='Z')||('a'<=B[n]&&B[n]<='z')||('0'<=B[n]&&B[n]<='9')){
n++;
}
i=m;
while(i){
A[i]=A[i-1],i--;
}
i=n;
while(i){
B[i]=B[i-1],i--;
}
A[0]=B[0]='\0';
make_prefix();
for (i = 1; i <= n; ++i){
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == m){
q = pi[m];
if (np<1000){
pos[np]=i-m;
}
np++;
}
}
fprintf(fout,"%d\n", np);
for (i=0;i<((np<1000)?np:1000);i++){
fprintf(fout,"%d ",pos[i]);
}
fprintf(fout,"\n");
fclose(fin);
fclose(fout);
return 0;
}