Pagini recente » Cod sursa (job #1614260) | Cod sursa (job #915306) | Cod sursa (job #850274) | Cod sursa (job #2903156) | Cod sursa (job #410606)
Cod sursa(job #410606)
#include <stdio.h>
#define MAX 200010
char A[MAX],B[MAX];
int pi[MAX],pos[1024],np=0,m=0,n=0;
void makePrefix(){
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(){
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
fgets(A,MAX,fin);
fgets(B,MAX,fin);
int q=0,i;
while((A[m]>= 'A'&&A[m]<='Z')||(A[m]>='a'&&A[m]<='z')||(A[m]>='0'&&A[m]<='9')){
m++;
}
while((B[n]>= 'A'&&B[n]<='Z')||(B[n]>='a'&&B[n]<='z')||(B[n]>='0'&&B[n]<='9')){
n++;
}
i=m+1;
while(i--)A[i]=A[i-1];
i=n+1;
while(i--)B[i]=B[i-1];
A[0]=B[0]=' ';
makePrefix();
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];
pos[np++]=i-m;
}
}
fprintf(fout,"%u\n",np);
np=(np>1000)?1000:np;
for(i=0;i<np;i++){
fprintf(fout,"%u ",pos[i]);
}
fclose(fin);
fclose(fout);
return 0;
}