chromium/components/zucchini/suffix_array.h

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40285824): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#ifndef COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_
#define COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_

#include <algorithm>
#include <iterator>
#include <numeric>
#include <vector>

#include "base/check.h"
#include "base/containers/adapters.h"

namespace zucchini {

// A functor class that implements the naive suffix sorting algorithm that uses
// std::sort with lexicographical compare. This is only meant as reference of
// the interface.
class NaiveSuffixSort { … };

// A functor class that implements suffix array induced sorting (SA-IS)
// algorithm with linear time and memory complexity,
// see http://ieeexplore.ieee.org/abstract/document/5582081/
class InducedSuffixSort { … };

// Generates a sorted suffix array for the input string |str| using the functor
// |Algorithm| which provides an interface equivalent to NaiveSuffixSort.
/// Characters found in |str| are assumed to be in range [0, |key_bound|).
// Returns the suffix array as a vector.
// |StrRng| is an input random access range.
// |KeyType| is an unsigned integer type.
template <class Algorithm, class StrRng, class KeyType>
std::vector<typename StrRng::size_type> MakeSuffixArray(const StrRng& str,
                                                        KeyType key_bound) { … }

// Type requirements:
// |SARng| is an input random access range.
// |StrIt1| is a random access iterator.
// |StrIt2| is a forward iterator.
template <class SARng, class StrIt1, class StrIt2>
// Lexicographical lower bound using binary search for
// [|str2_first|, |str2_last|) in the suffix array |suffix_array| of a string
// starting at |str1_first|. This does not necessarily return the index of
// the longest matching substring.
auto SuffixLowerBound(const SARng& suffix_array,
                      StrIt1 str1_first,
                      StrIt2 str2_first,
                      StrIt2 str2_last) -> decltype(std::begin(suffix_array)) { … }

}  // namespace zucchini

#endif  // COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_