Cod sursa(job #170239)

Utilizator fogabFodor Gabor fogab Data 2 aprilie 2008 16:12:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
// Rabin-Karp
// Do not confuse him with Robin Hood

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <vector.h>

using namespace std;

#define MAXN 2000100
#define BS 103      
#define BS2 73      
#define MOD 100003 
#define MOD2 100021



int sol[MAXN], nr;

int main(void){
    
/************ 
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");  

    string s1,s2;
        
    getline(fin,s2);
    getline(fin,s1); 
    
    int n = s1.size(),
        m = s2.size(),
        i,j;    
************/
    
    freopen("strmatch.in","r",stdin);  
    freopen("strmatch.out","w",stdout);    
     
    char s1[MAXN] , s2[MAXN];
     
    scanf("%s%s",s2,s1);  
    int n = strlen(s1),
        m = strlen(s2),
        i,j;
         
    int h2 = 0,h1 = 0,br = 1,
        hh1 = 0,hh2 = 0, br2 = 1;

    for (i = 0;i < m; i++){
        h1 = (h1 * BS + s1[i]) % MOD;
        h2 = (h2 * BS + s2[i]) % MOD;  
        if (i) br = (br * BS ) % MOD;
        hh1 = (hh1 * BS2 + s1[i]) % MOD2;
        hh2 = (hh2 * BS2 + s2[i]) % MOD2;  
        if (i) br2 = (br2 * BS2) % MOD2;        
        }  
    
    
    for (i = m-1;i<n;i++){
          j = 0;
          //fout << h1 << " " << h2 << "\n ";
          if (h1 == h2 && hh1 == hh2){
             /*                 
             for (j=0;j<m;j++){
                 if (s1[i-j] != s2[m-j-1]) j = m+5;
                 }*/
             j = m;    
             if (j == m){
                 sol[nr++] = (i - m +1);
                }                          
             }
          h1 = (((h1 - (s1[i - m + 1]*br % MOD) + MOD) % MOD) * BS + s1[i+1]) % MOD;
          hh1 = (((hh1 - (s1[i - m + 1]*br2 % MOD2) + MOD2) % MOD2) * BS2 + s1[i+1]) % MOD2;          
          }

     printf("%d\n" , nr);  
     
     if (nr > 1000) nr = 1000;
     
     for (i=0; i<nr; i++)       
         printf("%d ", sol[i]);

/************    
    fout << nr << "\n";
    
    if (nr > 1000) nr = 1000;
    
    for (i=0;i<nr;i++)      
      fout << sol[i] << " ";
  
    fin.close();
    fout.close();        
************/
    return 0;
}