Pagini recente » Cod sursa (job #474633) | Cod sursa (job #1326775) | Cod sursa (job #2022597) | Cod sursa (job #1058675) | Cod sursa (job #171319)
Cod sursa(job #171319)
#include <stdio.h>
#include <string.h>
#define NMAX 2001
const int d=62;
const long q1=100007;
const long q2=100021;
char s[NMAX],p[NMAX];
long ls,lp;
long h1,h2;
long poz[NMAX];
void hash(long &hp, long &hs, long q){
long i;hs=0,hp=0;
for (i=0;i<lp;i++){
hp=(d*hp+p[i])%q;
hs=(d*hs+s[i])%q;
}
}
long putere(long b, long c){
long aux;
if (b==1) return d; else {
if (b%2==1){aux=(putere(b-1,c )*d)%c; return aux;}
else {aux=putere(b/2,c); return (aux*aux)%c;}
}
}
void recalc_hash(long &hs1,long &hs2, long 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(){
long 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);
h1=putere(lp-1,q1);
h2=putere(lp-1,q2);
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;
}