Cod sursa(job #171319)

Utilizator nimeniaPaul Grigoras nimenia Data 4 aprilie 2008 00:13:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#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;  
}