string_searcher_rep Class Reference

#include <fast_search.hpp>

Inheritance diagram for string_searcher_rep:

Collaboration diagram for string_searcher_rep:

Public Member Functions
	string_searcher_rep (string s)
string	get_string ()
int	search_next (string what, int pos)
array< int >	search_all (string what)

Private Member Functions
array< int >	search_sub (string what)
Private Member Functions inherited from concrete_struct
	concrete_struct ()
	Default constructor for the concrete object. Increments the reference count.
virtual	~concrete_struct ()
	Virtual destructor for the concrete object. Decrements the reference count.

Private Attributes
string	s
array< hashmap< int, array< int > > >	a
Private Attributes inherited from concrete_struct
int	ref_count
	The reference count for the concrete object.

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

Detailed Description

Definition at line 20 of file fast_search.hpp.

Constructor & Destructor Documentation

string_searcher_rep()

string_searcher_rep::string_searcher_rep

(

string

s

)

Definition at line 47 of file fast_search.cpp.

                                                   : s (s2), a () {
  // NOTE: a[i] contains a hashmap with all associations c :-> j,
  // where c is the hash code of the substring s (j, j + 2^i).
  int        i, n= N (s);
  array<int> codes (n);
  for (i= 0; i < n; i++)
    codes[i]= (int) (unsigned int) (unsigned char) s[i];
  int l= 1;
  while (l <= n) {
    hashmap<int, array<int>> h;
    for (i= 0; i + l <= n; i++) {
      int c= codes[i];
      if (!h->contains (c)) h (c)= array<int> ();
      h (c) << i;
    }
    a << h;
    int d= 2 * l;
    for (i= 0; i + d <= n; i++)
      codes[i]= hash_combine (codes[i], codes[i + l], l);
    l= d;
  }
}

Member Function Documentation

search_sub()

array< int > string_searcher_rep::search_sub ( string what )

private

Definition at line 80 of file fast_search.cpp.

                                            {
  if (N (what) == 0) {
    array<int> r;
    for (int i= 0; i <= N (s); i++)
      r << i;
    return r;
  }
  int k= 1, l= 0;
  while ((k << 1) <= N (what)) {
    k<<= 1;
    l++;
  }
  int code= fast_hash (what (0, k));
  if (!a[l]->contains (code)) return array<int> ();
  else return a[l][code];
}

get_string()

string string_searcher_rep::get_string

(

)

Definition at line 71 of file fast_search.cpp.

                                 {
  return s;
}

search_next()

int string_searcher_rep::search_next	(	string	what,
		int	pos )

Definition at line 98 of file fast_search.cpp.

                                                      {
  array<int> ps= search_sub (what);
  for (int i= 0; i < N (ps); i++) {
    int next= ps[i];
    if (next >= pos && test (s, next, what)) return next;
  }
  return -1;
}

search_all()

array< int > string_searcher_rep::search_all

(

string

what

)

Definition at line 108 of file fast_search.cpp.

                                            {
  // NOTE: There are better algorithms based on generalized suffix trees.
  // However, in practice, our approach based on hashtables might be faster
  array<int> r;
  array<int> ps= search_sub (what);
  for (int i= 0; i < N (ps); i++) {
    int pos= ps[i];
    if (test (s, pos, what)) r << pos;
  }
  return r;
}

Friends And Related Symbol Documentation

string_searcher

friend class string_searcher

friend

Definition at line 30 of file fast_search.hpp.

get_longest_common

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

friend

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;
          }
        }
      }
    }
  }
}

Member Data Documentation

s

string string_searcher_rep::s

private

Definition at line 21 of file fast_search.hpp.

a

array<hashmap<int, array<int> > > string_searcher_rep::a

private

Definition at line 22 of file fast_search.hpp.

---

The documentation for this class was generated from the following files:

• fast_search.hpp
• fast_search.cpp