All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
lcp.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Smulewicz
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_LCP_HPP
16 #define PAAL_LCP_HPP
17 
18 #include <vector>
19 
20 namespace paal {
36 template <typename Letter>
37 void lcp(std::vector<int> const &suffix_array, std::vector<int> const &rank,
38  std::vector<int> &lcp, std::vector<Letter> const &sumWords) {
39  int comonPrefixLength = 0;
40  for (auto suffixRank :
41  rank) { // suffixRank number suffix in lexicographically order
42  if (suffixRank != 0) {
43  while (sumWords[suffix_array[suffixRank] + comonPrefixLength] ==
44  sumWords[suffix_array[suffixRank - 1] + comonPrefixLength]) {
45  ++comonPrefixLength;
46  }
47  }
48  lcp[suffixRank] = comonPrefixLength;
49  if (comonPrefixLength > 0) {
50  --comonPrefixLength;
51  }
52  }
53 }
54 }
55 
56 #endif // PAAL_LCP_HPP
void lcp(std::vector< int > const &suffix_array, std::vector< int > const &rank, std::vector< int > &lcp, std::vector< Letter > const &sumWords)
fill array lcp lcp[0] is undefined and lcp[i] stores the largest common prefix of the lexicographical...
Definition: lcp.hpp:37
void suffix_array(std::vector< Letter > &text, std::vector< int > &SA, Letter max_letter=0)
detail
void rank(std::vector< T > const &m_id_to_t, std::vector< Idx > &m_t_to_id, int INVALID_IDX=0)
computes rank i.e. index of element in range
Definition: bimap.hpp:364