Pagini recente » Cod sursa (job #2548014) | Cod sursa (job #160440) | Cod sursa (job #770697) | Cod sursa (job #2482770) | Cod sursa (job #171327)
Cod sursa(job #171327)
#include <stdio.h>
#include <string.h>
#define NMAX 2000001
const int d=73;
const int q1=100007;
const int q2=100021;
char s[NMAX],p[NMAX];
int ls,lp;
int h1=1,h2=1;
int poz[NMAX];
void hash(int &hp, int &hs, int q){
int i;hs=0,hp=0;
for (i=0;i<lp;i++){
hp=(d*hp+p[i])%q;
hs=(d*hs+s[i])%q;
if (q==q1 ) {if (i) h1=(d*h1)%q1,h2=(d*h2)%q2;}
}
}
void recalc_hash(int &hs1,int &hs2, int i){
hs1=((hs1-(s[i-lp]*h1)%q1+q1)*d+s[i])%q1;
hs2=((hs2-(s[i-lp]*h2)%q2+q2)*d+s[i])%q2;
}
int main(){
int hashp1,hashp2,hashs1,hashs2,j,i,ok,nr=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out", "w",stdout);
scanf("%s %s",p,s);
lp=strlen(p);
ls=strlen(s);
hash(hashp1,hashs1,q1);
hash(hashp2,hashs2,q2);
if (hashs1==hashp1 && hashs2==hashp2) {
for (ok=1,i=0;i<lp && ok;i++) if (s[i]!=p[i]) ok=0;
if (ok) {nr++; poz[nr-1]=0;}
}
for (i=lp;i<ls && nr<1000;i++){
recalc_hash(hashs1,hashs2,i);
if (hashs1==hashp1 && hashs2==hashp2){
for (ok=1, j=0;j<lp && ok;j++) if (s[i-lp+j+1]!=p[j]) ok=0;
if (ok) {nr++; poz[nr-1]=i-lp+1;}
}
}
printf("%d\n",nr);
for(i=0;i<nr;i++) printf("%d ",poz[i]);
return 0;
}