Pagini recente » Cod sursa (job #2933783) | Cod sursa (job #2848581) | Cod sursa (job #1049222) | Cod sursa (job #2720254) | Cod sursa (job #320262)
Cod sursa(job #320262)
#include<stdio.h>
#define nmax 2000010
char a[nmax],b[nmax];
void pref();
void kmp();
int min(int,int);
int n,m,p1[nmax],p2[2000],n1;
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
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++;
for(int i=m;i!=0;i--){
a[i]=a[i-1];
a[0]=' ';
}
for(int i=n;i!=0;i--){
b[i]=b[i-1];
b[0]=' ';
}
pref();
kmp();
printf("%d\n",n1);
for(int i=1;i<=min(n1,1000);i++)
printf("%d ",p2[i]);
printf("\n");
return 0;
}
void pref(){
int i,c=0;
for(i=2,p1[1]=0;i<=m;i++){
while(c&&a[c+1]!=a[i])
c=p1[c];
if(a[c+1]==a[i])
c++;
p1[i]=c;
}
}
void kmp(){
int i,c=0;
for(i=1;i<=n;i++){
while(c&&a[c+1]!=b[i])
c=p1[c];
if(a[c+1]==b[i])
c++;
if(c==m){
c=p1[m];
n1++;
if(n1<=1000)
p2[n1]=i-m;
}
}
}
int min(int a,int b){
if(a<b)return a;
else return b;
}