minimal_string.hpp¶

#include "noya/minimal_string.hpp"

SourceExpanded

#ifndef NOYA_MINIMAL_STRING_HPP
#define NOYA_MINIMAL_STRING_HPP 1

#include <algorithm>
#include <string>
#include <vector>

namespace noya {

/// @brief Find the starting index of the lexicographically smallest rotation.
template <class T> int minimal_string_index(const std::vector<T> &sec) {
  int k = 0, i = 0, j = 1, n = sec.size();
  while (k < n && i < n && j < n) {
    if (sec[(i + k) % n] == sec[(j + k) % n]) {
      k++;
    } else {
      if (sec[(i + k) % n] > sec[(j + k) % n])
        i = i + k + 1;
      else
        j = j + k + 1;
      if (i == j)
        i++;
      k = 0;
    }
  }
  return std::min(i, j);
}

/// @brief Return the lexicographically smallest rotation of the sequence.
template <class T> std::vector<T> minimal_string(const std::vector<T> &sec) {
  if (sec.empty())
    return {};
  int start = minimal_string_index(sec);
  std::vector<T> ret(sec.size());
  std::rotate_copy(sec.begin(), sec.begin() + start, sec.end(), ret.begin());
  return ret;
}

inline std::string minimal_string(const std::string &sec) {
  if (sec.empty())
    return "";
  int start = minimal_string_index(std::vector<char>(sec.begin(), sec.end()));
  return sec.substr(start) + sec.substr(0, start);
}

} // namespace noya

#endif // NOYA_MINIMAL_STRING_HPP

#include <algorithm>
#include <string>
#include <vector>

namespace noya {

/// @brief Find the starting index of the lexicographically smallest rotation.
template <class T> int minimal_string_index(const std::vector<T> &sec) {
  int k = 0, i = 0, j = 1, n = sec.size();
  while (k < n && i < n && j < n) {
    if (sec[(i + k) % n] == sec[(j + k) % n]) {
      k++;
    } else {
      if (sec[(i + k) % n] > sec[(j + k) % n])
        i = i + k + 1;
      else
        j = j + k + 1;
      if (i == j)
        i++;
      k = 0;
    }
  }
  return std::min(i, j);
}

/// @brief Return the lexicographically smallest rotation of the sequence.
template <class T> std::vector<T> minimal_string(const std::vector<T> &sec) {
  if (sec.empty())
    return {};
  int start = minimal_string_index(sec);
  std::vector<T> ret(sec.size());
  std::rotate_copy(sec.begin(), sec.begin() + start, sec.end(), ret.begin());
  return ret;
}

inline std::string minimal_string(const std::string &sec) {
  if (sec.empty())
    return "";
  int start = minimal_string_index(std::vector<char>(sec.begin(), sec.end()));
  return sec.substr(start) + sec.substr(0, start);
}

} // namespace noya