Pagini recente » Cod sursa (job #1307574) | Cod sursa (job #2384196) | Cod sursa (job #1910097) | Cod sursa (job #1963472) | Cod sursa (job #153852)
Cod sursa(job #153852)
#include<cstdio>
#include<cstring>
const long MAX=2000100;
long pi[MAX],nr,n,m,i,rez[1010];
char s[MAX],s1[MAX];
void prefix(){
long k,i;
// n=strlen(s1);
k=0;pi[1]=0;
for(i=2;i<n;i++){
while(k>0 && s1[k+1]!=s1[i])
k=pi[k];
if(s1[k+1]==s1[i])
k++;
pi[i]=k;
}
}
void kmp(){
long k,i;
// n=strlen(s1);m=strlen(s);
k=0;
for(i=1;i<m;i++){
while(k>0 && s1[k+1]!=s[i])
k=pi[k];
if(s1[k+1]==s[i])
k++;
if(k==n-1){
if(nr<1000)
rez[nr++]=i-n+2;
else
nr++;
k=pi[n-1];
}
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,MAX,stdin);
fgets(s+1,MAX,stdin);
n=1;m=1;
for(;s[m]>='a' && s[m]<='z' || s[m]>='A' && s[m]<='Z' || s[m]>='0' && s[m]<='9';m++);
for(;s1[n]>='a' && s1[n]<='z' || s1[n]>='A' && s1[n]<='Z' || s1[n]>='0' && s1[n]<='9';n++);
/*for(i=1;i<n;i++)
printf("%c",s1[i]);
printf("\n");
for(i=1;i<m;i++)
printf("%c",s[i]);*/
nr=0;
prefix();
kmp();
printf("%ld\n",nr);
for(i=0;i<nr && i<1000;i++)
printf("%ld ",rez[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}