fast_search.cpp File Reference

#include "fast_search.hpp"
#include "analyze.hpp"
#include "iterator.hpp"

Include dependency graph for fast_search.cpp:

Go to the source code of this file.

Functions
static int	hash_combine (int c1, int c2, int l)
static int	fast_hash (string s)
void	get_longest_common (string s1, string s2, int &b1, int &e1, int &b2, int &e2)

Function Documentation

hash_combine()

static int hash_combine ( int c1, int c2, int l )

static

Definition at line 21 of file fast_search.cpp.

                                     {
  // FIXME: we should rather compute modulo 2^32 - 1 instead of 2^32,
  // or modulo some prime number < 2^32, and avoid the cyclicity of period 32
  int rot= (9 * l) & 31;
  if (rot == 0) return c1 ^ c2;
  unsigned int u1= c1;
  unsigned int u2= c2;
  unsigned int r2=
      ((u2 << rot) & 0xffffffff) ^ ((u2 >> (32 - rot)) & 0xffffffff);
  return (int) (u1 ^ r2);
}

fast_hash()

static int fast_hash ( string s )

static

Definition at line 34 of file fast_search.cpp.

                     {
  unsigned int h= 0;
  for (int i= N (s) - 1; i >= 0; i--) {
    h= ((h << 9) & 0xffffffff) ^ ((h >> 23) & 0xffffffff);
    h= h ^ ((unsigned int) (unsigned char) s[i]);
  }
  return (int) h;
}

get_longest_common()

void get_longest_common	(	string	s1,
		string	s2,
		int &	b1,
		int &	e1,
		int &	b2,
		int &	e2 )

Definition at line 125 of file fast_search.cpp.

                                                                              {
  // NOTE: There are better algorithms based on generalized suffix trees.
  b1= e1= b2= e2       = 0;
  int             bestl= 0;
  string_searcher ss1 (s1);
  string_searcher ss2 (s2);
  for (int i= min (N (ss1->a), N (ss2->a)) - 1; i >= 0; i--) {
    hashmap<int, array<int>> a1= ss1->a[i];
    hashmap<int, array<int>> a2= ss2->a[i];
    iterator<int>            it= iterate (a1);
    while (it->busy ()) {
      int        h  = it->next ();
      array<int> ps1= a1[h];
      array<int> ps2= a2[h];
      if (N (ps1) == 0 || N (ps2) == 0) continue;
      for (int j1= 0; j1 < N (ps1); j1++) {
        int pos1= ps1[j1];
        if (b1 <= pos1 && pos1 < e1) continue;
        for (int j2= 0; j2 < N (ps2); j2++) {
          int pos2= ps2[j2];
          int bb1= pos1, ee1= pos1, bb2= pos2, ee2= pos2;
          while (bb1 > 0 && bb2 > 0 && s1[bb1 - 1] == s2[bb2 - 1]) {
            bb1--;
            bb2--;
          }
          while (ee1 < N (s1) && ee2 < N (s2) && s1[ee1] == s2[ee2]) {
            ee1++;
            ee2++;
          }
          if (ee1 - bb1 > bestl ||
              (ee1 - bb1 == bestl && (bb1 < b1 || (bb1 == b1 && bb2 < b2)))) {
            b1   = bb1;
            e1   = ee1;
            b2   = bb2;
            e2   = ee2;
            bestl= e1 - b1;
          }
        }
      }
    }
  }
}