Pagini recente » Cod sursa (job #760610) | Cod sursa (job #160309) | Cod sursa (job #550839) | Cod sursa (job #3225227) | Cod sursa (job #1511012)
#include<cstdio>
#include<cstring>
#define base 101
#define mod1 100007
#define mod2 100021
using namespace std;
char a[2000010],b[2000010],sol[2000010];
int m,n;
int verif(int p){
int i;
for(i=0;i<m;i++)
if(a[i]!=b[i+p])
return 0;
return 1;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int hash1_a=0,hash2_a=0,hash1=0,hash2=0,last1=1,last2=1,match=0,i;
scanf("%s%s",&a,&b);
m=strlen(a);
n=strlen(b);
if(m>n){
printf("0");
return 0;
}
for(i=1;i<=m-1;i++){
last1=(last1*base)%mod1;
last2=(last2*base)%mod2;
}
for(i=0;i<m;i++){
hash1_a=(hash1_a*base+a[i])%mod1;
hash2_a=(hash2_a*base+a[i])%mod2;
hash1=(hash1*base+b[i])%mod1;
hash2=(hash2*base+b[i])%mod2;
}
if(hash1==hash1_a&&hash2==hash2_a)
if(verif(0)==1){
match++;
sol[0]=1;
}
for(i=m;i<n;i++){
hash1=(((hash1-(b[i-m]*last1)%mod1+mod1)%mod1)*base+b[i])%mod1;
hash2=(((hash2-(b[i-m]*last2)%mod2+mod2)%mod2)*base+b[i])%mod2;
if(hash1==hash1_a&&hash2==hash2_a)
if(verif(i-m+1)==1){
match++;
sol[i-m+1]=1;
}
}
printf("%d\n",match);
match=0;
for(i=0;i<n&&match<1000;i++)
if(sol[i]==1){
printf("%d ",i);
match++;
}
return 0;
}