Cod sursa(job #169755)

Utilizator fogabFodor Gabor fogab Data 1 aprilie 2008 22:16:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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          // base
#define MOD 100007  // 10 digits, nice one

int sol[MAXN], nr;

int main(void){

    ifstream fin("strmatch.in");
    ofstream fout("strmacth.out");

    string s1,s2;
        
    getline(fin,s2);
    getline(fin,s1);

    int n = s1.size(),
        m = s2.size(),
        i,j;
    
    s1 = s1 + '!';
     
    int h2 = 0,h1 = 0,br = 1;

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

    return 0;
}