Cod sursa(job #171325)

Utilizator nimeniaPaul Grigoras nimenia Data 4 aprilie 2008 00:45:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#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("strmatch2.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;  
}