/**
 * File: DC3.h
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * Implementation of the DC3 algorithm (sometimes called the skew algorithm)
 * for constructing suffix arrays. This was the first linear-time algorithm for
 * building suffix arrays that did not rely on going through suffix trees as an
 * intermediary step. It performs well in practice but is not as fast as other
 * linear-time construction algorithms like SA-IS.
 *
 * This implementation relies on the implementation of the Manber-Myers
 * algorithm for suffix array construction, also availble on the Archive of
 * Interesting Code. You can find it at
 *
 *   www.keithschwarz.com/interesting/code/?dir=manber-myers
 *
 */
#ifndef DC3_Included
#define DC3_Included

#include "ManberMyers.h"

/* Computes a suffix array using the DC3 algorithm. As with the Manber-Myers
 * algorithm, this implementation assumes that the input text string has been
 * suffixed with a sentinel and had each of its characters remapped to its rank
 * among all characters.
 */
SuffixArray dc3(const std::vector<std::size_t>& text);

#endif