test/library-checker/number_of_substrings.test.cpp

• View this file on GitHub
• Last update: 2022-04-06 16:00:36+09:00
• Problem: https://judge.yosupo.jp/problem/number_of_substrings

Depends on

• Suffix Array (src/string/suffix_array.hpp)
• Iterator Category (src/utils/iterator/category.hpp)
• Reverse Iterator (src/utils/iterator/reverse.hpp)
• Zip (src/utils/py-like/zip.hpp)
• SFINAE (src/utils/sfinae.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/number_of_substrings"

#include <iostream>

#include "src/string/suffix_array.hpp"
#include "src/utils/py-like/zip.hpp"

int main() {
  std::string s;
  std::cin >> s;
  workspace::suffix_array sa(s);
  long long ans = 0;
  for (auto &&[x, y] : workspace::zip(sa, sa.lcp_array())) {
    ans += s.size() - x - y;
  }
  printf("%lld\n", ans);
}

#line 1 "test/library-checker/number_of_substrings.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/number_of_substrings"

#include <iostream>

#line 2 "src/string/suffix_array.hpp"

/*
 * @file suffix_array.hpp
 * @brief Suffix Array
 */

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

#line 2 "src/utils/sfinae.hpp"

/**
 * @file sfinae.hpp
 * @brief SFINAE
 */

#include <cstdint>
#include <iterator>
#include <type_traits>

#ifndef __INT128_DEFINED__

#ifdef __SIZEOF_INT128__
#define __INT128_DEFINED__ 1
#else
#define __INT128_DEFINED__ 0
#endif

#endif

namespace std {

#if __INT128_DEFINED__

template <> struct make_signed<__uint128_t> { using type = __int128_t; };
template <> struct make_signed<__int128_t> { using type = __int128_t; };

template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; };
template <> struct make_unsigned<__int128_t> { using type = __uint128_t; };

template <> struct is_signed<__uint128_t> : std::false_type {};
template <> struct is_signed<__int128_t> : std::true_type {};

template <> struct is_unsigned<__uint128_t> : std::true_type {};
template <> struct is_unsigned<__int128_t> : std::false_type {};

#endif

}  // namespace std

namespace workspace {

template <class Tp, class... Args> struct variadic_front { using type = Tp; };

template <class... Args> struct variadic_back;

template <class Tp> struct variadic_back<Tp> { using type = Tp; };

template <class Tp, class... Args> struct variadic_back<Tp, Args...> {
  using type = typename variadic_back<Args...>::type;
};

template <class type, template <class> class trait>
using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;

/**
 * @brief Return type of subscripting ( @c [] ) access.
 */
template <class _Tp>
using subscripted_type =
    typename std::decay<decltype(std::declval<_Tp&>()[0])>::type;

template <class Container>
using element_type = typename std::decay<decltype(*std::begin(
    std::declval<Container&>()))>::type;

template <class _Tp, class = void> struct has_begin : std::false_type {};

template <class _Tp>
struct has_begin<
    _Tp, std::__void_t<decltype(std::begin(std::declval<const _Tp&>()))>>
    : std::true_type {
  using type = decltype(std::begin(std::declval<const _Tp&>()));
};

template <class _Tp, class = void> struct has_size : std::false_type {};

template <class _Tp>
struct has_size<_Tp, std::__void_t<decltype(std::size(std::declval<_Tp>()))>>
    : std::true_type {};

template <class _Tp, class = void> struct has_resize : std::false_type {};

template <class _Tp>
struct has_resize<_Tp, std::__void_t<decltype(std::declval<_Tp>().resize(
                           std::declval<size_t>()))>> : std::true_type {};

template <class _Tp, class = void> struct has_mod : std::false_type {};

template <class _Tp>
struct has_mod<_Tp, std::__void_t<decltype(_Tp::mod)>> : std::true_type {};

template <class _Tp, class = void> struct is_integral_ext : std::false_type {};
template <class _Tp>
struct is_integral_ext<
    _Tp, typename std::enable_if<std::is_integral<_Tp>::value>::type>
    : std::true_type {};

#if __INT128_DEFINED__

template <> struct is_integral_ext<__int128_t> : std::true_type {};
template <> struct is_integral_ext<__uint128_t> : std::true_type {};

#endif

#if __cplusplus >= 201402

template <class _Tp>
constexpr static bool is_integral_ext_v = is_integral_ext<_Tp>::value;

#endif

template <typename _Tp, typename = void> struct multiplicable_uint {
  using type = uint_least32_t;
};
template <typename _Tp>
struct multiplicable_uint<
    _Tp,
    typename std::enable_if<(2 < sizeof(_Tp)) &&
                            (!__INT128_DEFINED__ || sizeof(_Tp) <= 4)>::type> {
  using type = uint_least64_t;
};

#if __INT128_DEFINED__

template <typename _Tp>
struct multiplicable_uint<_Tp,
                          typename std::enable_if<(4 < sizeof(_Tp))>::type> {
  using type = __uint128_t;
};

#endif

template <typename _Tp> struct multiplicable_int {
  using type =
      typename std::make_signed<typename multiplicable_uint<_Tp>::type>::type;
};

template <typename _Tp> struct multiplicable {
  using type = std::conditional_t<
      is_integral_ext<_Tp>::value,
      std::conditional_t<std::is_signed<_Tp>::value,
                         typename multiplicable_int<_Tp>::type,
                         typename multiplicable_uint<_Tp>::type>,
      _Tp>;
};

template <class> struct first_arg { using type = void; };

template <class _R, class _Tp, class... _Args>
struct first_arg<_R(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _R, class _Tp, class... _Args>
struct first_arg<_R (*)(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...) const> {
  using type = _Tp;
};

template <class _Tp, class = void> struct parse_compare : first_arg<_Tp> {};

template <class _Tp>
struct parse_compare<_Tp, std::__void_t<decltype(&_Tp::operator())>>
    : first_arg<decltype(&_Tp::operator())> {};

template <class _Container, class = void> struct get_dimension {
  static constexpr size_t value = 0;
};

template <class _Container>
struct get_dimension<_Container,
                     std::enable_if_t<has_begin<_Container>::value>> {
  static constexpr size_t value =
      1 + get_dimension<typename std::iterator_traits<
              typename has_begin<_Container>::type>::value_type>::value;
};

}  // namespace workspace
#line 13 "src/string/suffix_array.hpp"

namespace workspace {

/*
 * @class suffix_array
 * @brief construct SA and LCP array.
 * @tparam str_type the type of string
 */
template <class str_type> class suffix_array {
  str_type str;
  std::vector<size_t> sa, rank, lcp;

  void construct_sa() {
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(),
              [&](size_t i, size_t j) { return str[i] < str[j]; });

    for (size_t r{1}, c{}, *ptr{&sa.front()}, *tmp{ptr}; c != size();
         ++r, ptr = tmp)
      while (c != size() && str[*ptr] == str[*tmp]) ++c, rank[*tmp++] = r;

    for (size_t k{1}; k < size(); k <<= 1) {
      auto comp = [&](size_t i, size_t j) -> bool {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        return (i + k < size() ? rank[i + k] : 0) <
               (j + k < size() ? rank[j + k] : 0);
      };
      std::sort(sa.begin(), sa.end(), comp);

      std::vector<size_t> next_rank(size());
      for (size_t r{1}, c{}, *ptr{&sa.front()}, *tmp{ptr}; c != size();
           ++r, ptr = tmp)
        while (c != size() && !comp(*ptr, *tmp)) ++c, next_rank[*tmp++] = r;
      rank.swap(next_rank);
    }

    sa.emplace(sa.begin(), size());
    rank.emplace_back(0);
  }

  void construct_lcp() {
    for (size_t i{}, h{}; i != size(); ++i, h = h ? h - 1 : 0) {
      for (size_t j{sa[rank[i] - 1] + h}; i + h != size() && j != size();
           ++j, ++h)
        if (str[i + h] != str[j]) break;
      lcp[rank[i] - 1] = h;
    }
  }

 public:
  static constexpr size_t npos = -1;
  using char_type = element_type<str_type>;

  std::vector<size_t>::const_iterator begin() const { return sa.begin() + 1; }

  std::vector<size_t>::const_iterator end() const { return sa.end(); }

  /*
   * @fn operator[]
   * @brief find the i-th suffix
   * @param i the rank
   * @return index of the suffix
   */
  size_t operator[](size_t i) const { return sa[i + 1]; }

  /*
   * @fn size
   * @return length of the string
   */
  size_t size() const { return std::size(str); }

  template <class type = str_type, typename = typename type::value_type>
  suffix_array(const str_type &_str)
      : str(_str), sa(size()), rank(size()), lcp(size()) {
    construct_sa();
    construct_lcp();
  }

  template <class type = str_type, std::enable_if_t<std::is_array<type>::value,
                                                    std::nullptr_t> = nullptr>
  suffix_array(const str_type &_str) : sa(size()), rank(size()), lcp(size()) {
    std::copy(std::begin(_str), std::end(_str), str);
    construct_sa();
    construct_lcp();
  }

  /*
   * @fn find
   * @brief find (key) as a substring
   * @param key
   * @return index if found, npos if not found
   */
  size_t find(const str_type &key) const {
    using std::begin;
    using std::end;

    size_t lower{npos}, upper{size()};
    while (upper - lower > 1) {
      size_t mid = (lower + upper) >> 1;
      bool less = false;
      for (auto i{begin(str) + sa[mid]}, j{begin(key)}; j != end(key);
           ++i, ++j) {
        if (i == end(str) || *i < *j) {
          less = true;
          break;
        }
        if (*i > *j) break;
      }
      (less ? lower : upper) = mid;
    }

    if (upper == size()) return npos;
    for (auto i{begin(str) + sa[upper]}, j{begin(key)}; j != end(key); ++i, ++j)
      if (i == end(str) || *i != *j) return npos;
    return sa[upper];
  }

  /*
   * @return lengths of LCP of each adjacent pairs in the suffix
   * array
   */
  const std::vector<size_t> &lcp_array() const { return lcp; }
};

}  // namespace workspace
#line 2 "src/utils/py-like/zip.hpp"

/**
 * @file zip.hpp
 * @brief Zip
 */

#include <cstddef>
#include <tuple>
#line 11 "src/utils/py-like/zip.hpp"

#line 2 "src/utils/iterator/category.hpp"

/*
 * @file category.hpp
 * @brief Iterator Category
 */

#line 10 "src/utils/iterator/category.hpp"

namespace workspace {

/*
 * @tparam Tuple Tuple of iterator types
 */
template <class Tuple, size_t N = std::tuple_size<Tuple>::value - 1>
struct common_iterator_category {
  using type = typename std::common_type<
      typename common_iterator_category<Tuple, N - 1>::type,
      typename std::iterator_traits<typename std::tuple_element<
          N, Tuple>::type>::iterator_category>::type;
};

template <class Tuple> struct common_iterator_category<Tuple, 0> {
  using type = typename std::iterator_traits<
      typename std::tuple_element<0, Tuple>::type>::iterator_category;
};

}  // namespace workspace
#line 2 "src/utils/iterator/reverse.hpp"

/*
 * @file reverse_iterator.hpp
 * @brief Reverse Iterator
 */

#if __cplusplus >= 201703L

#line 11 "src/utils/iterator/reverse.hpp"
#include <optional>

namespace workspace {

/*
 * @class reverse_iterator
 * @brief Wrapper class for `std::reverse_iterator`.
 * @see http://gcc.gnu.org/PR51823
 */
template <class Iterator>
class reverse_iterator : public std::reverse_iterator<Iterator> {
  using base_std = std::reverse_iterator<Iterator>;
  std::optional<typename base_std::value_type> deref;

 public:
  using base_std::reverse_iterator;

  constexpr typename base_std::reference operator*() noexcept {
    if (!deref) {
      Iterator tmp = base_std::current;
      deref = *--tmp;
    }
    return deref.value();
  }

  constexpr reverse_iterator &operator++() noexcept {
    base_std::operator++();
    deref.reset();
    return *this;
  }
  constexpr reverse_iterator &operator--() noexcept {
    base_std::operator++();
    deref.reset();
    return *this;
  }
  constexpr reverse_iterator operator++(int) noexcept {
    base_std::operator++();
    deref.reset();
    return *this;
  }
  constexpr reverse_iterator operator--(int) noexcept {
    base_std::operator++();
    deref.reset();
    return *this;
  }
};

}  // namespace workspace

#endif
#line 2 "lib/cxx17"

#line 2 "lib/cxx14"

#ifndef _CXX14_CONSTEXPR
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
#endif
#line 4 "lib/cxx17"

#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif

#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif

#line 22 "lib/cxx17"

#if __cplusplus < 201703L

namespace std {

/**
 *  @brief  Return the size of a container.
 *  @param  __cont  Container.
 */
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
    -> decltype(__cont.size()) {
  return __cont.size();
}

/**
 *  @brief  Return the size of an array.
 */
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
  return _Nm;
}

/**
 *  @brief  Return whether a container is empty.
 *  @param  __cont  Container.
 */
template <typename _Container>
[[nodiscard]] constexpr auto empty(const _Container& __cont) noexcept(
    noexcept(__cont.empty())) -> decltype(__cont.empty()) {
  return __cont.empty();
}

/**
 *  @brief  Return whether an array is empty (always false).
 */
template <typename _Tp, size_t _Nm>
[[nodiscard]] constexpr bool empty(const _Tp (&)[_Nm]) noexcept {
  return false;
}

/**
 *  @brief  Return whether an initializer_list is empty.
 *  @param  __il  Initializer list.
 */
template <typename _Tp>
[[nodiscard]] constexpr bool empty(initializer_list<_Tp> __il) noexcept {
  return __il.size() == 0;
}

struct monostate {};

}  // namespace std

#else

#include <variant>

#endif
#line 15 "src/utils/py-like/zip.hpp"

namespace workspace {

template <class _Tuple> class zipped : protected _Tuple {
 public:
  zipped(const _Tuple &__x) : _Tuple(__x) {}

  template <std::size_t _Nm> constexpr decltype(auto) get() const &noexcept {
    return *std::get<_Nm>(*this);
  }

  template <std::size_t _Nm> constexpr decltype(auto) get() &&noexcept {
    auto __tmp = *std::get<_Nm>(*this);
    return __tmp;
  }
};

template <class... _Containers> class zip {
  std::tuple<_Containers...> __c;

  template <std::size_t _Nm = 0>
  constexpr decltype(auto) begin_cat() const noexcept {
    if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers)) {
      return std::tuple_cat(std::tuple(std::begin(std::get<_Nm>(__c))),
                            begin_cat<_Nm + 1>());
    } else
      return std::tuple<>();
  }

  template <std::size_t _Nm = 0>
  constexpr decltype(auto) end_cat() const noexcept {
    if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers)) {
      return std::tuple_cat(std::tuple(std::end(std::get<_Nm>(__c))),
                            end_cat<_Nm + 1>());
    } else
      return std::tuple<>();
  }

  using _Iterator_tuple =
      std::tuple<decltype(std::begin(std::declval<_Containers>()))...>;

 public:
  using size_type = std::size_t;

  class iterator : public zipped<_Iterator_tuple> {
    using _Base = zipped<_Iterator_tuple>;

   public:
    using difference_type = std::ptrdiff_t;
    using value_type = _Base;
    using pointer = void;
    using reference = value_type &;
    using iterator_category =
        typename common_iterator_category<_Iterator_tuple>::type;

   protected:
    template <std::size_t _Nm = 0>
    constexpr bool equal(const iterator &__x) const noexcept {
      if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers)) {
        return std::get<_Nm>(*this) == std::get<_Nm>(__x) ||
               equal<_Nm + 1>(__x);
      } else
        return false;
    }

    template <std::size_t _Nm = 0> constexpr void increment() noexcept {
      if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers))
        ++std::get<_Nm>(*this), increment<_Nm + 1>();
    }

    template <std::size_t _Nm = 0> constexpr void decrement() noexcept {
      if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers))
        --std::get<_Nm>(*this), decrement<_Nm + 1>();
    }

    template <std::size_t _Nm = 0>
    constexpr void advance(difference_type __d) noexcept {
      if _CXX17_CONSTEXPR (_Nm != sizeof...(_Containers))
        std::get<_Nm>(*this) += __d, advance<_Nm + 1>(__d);
    }

   public:
    iterator(const _Iterator_tuple &__x) : _Base(__x) {}

    constexpr bool operator==(const iterator &__x) const noexcept {
      return equal(__x);
    }
    constexpr bool operator!=(const iterator &__x) const noexcept {
      return !equal(__x);
    }

    constexpr iterator &operator++() noexcept {
      increment();
      return *this;
    }
    constexpr iterator operator++(int) noexcept {
      auto __tmp = *this;
      increment();
      return __tmp;
    }

    constexpr iterator &operator--() noexcept {
      decrement();
      return *this;
    }
    constexpr iterator operator--(int) noexcept {
      auto __tmp = *this;
      decrement();
      return __tmp;
    }

    constexpr bool operator<(const iterator &__x) const noexcept {
      return std::get<0>(*this) < std::get<0>(__x);
    }
    constexpr bool operator<=(const iterator &__x) const noexcept {
      return std::get<0>(*this) <= std::get<0>(__x);
    }
    constexpr bool operator>(const iterator &__x) const noexcept {
      return !operator<=(__x);
    }
    constexpr bool operator>=(const iterator &__x) const noexcept {
      return !operator>(__x);
    }

    constexpr iterator &operator+=(difference_type __d) noexcept {
      advance(__d);
      return *this;
    }
    constexpr iterator &operator-=(difference_type __d) noexcept {
      advance(-__d);
      return *this;
    }
    constexpr iterator operator+(difference_type __d) const noexcept {
      return iterator{*this} += __d;
    }
    constexpr iterator operator-(difference_type __d) const noexcept {
      return iterator{*this} -= __d;
    }

    constexpr difference_type operator-(const iterator &__x) const noexcept {
      return std::get<0>(*this) - std::get<0>(__x);
    }

    constexpr reference operator*() noexcept { return {*this}; }
  };

  using const_iterator = iterator;

  template <class... _Args>
  constexpr zip(_Args &&...__args) noexcept
      : __c(std::forward<_Args>(__args)...) {}

  template <class... _Args>
  constexpr zip(std::initializer_list<_Args>... __args) noexcept
      : __c(std::forward<_Args>(__args)...) {}

  constexpr iterator begin() const noexcept { return {begin_cat()}; }

  constexpr iterator end() const noexcept { return {end_cat()}; }

  constexpr reverse_iterator<iterator> rbegin() const noexcept {
    return reverse_iterator<iterator>{end()};
  }

  constexpr reverse_iterator<iterator> rend() const noexcept {
    return reverse_iterator<iterator>{begin()};
  }

#if __cplusplus >= 201703L
  constexpr size_type size() const noexcept {
    size_type __n = -1;
    std::apply(
        [&__n](auto &&__x) {
          if (__n < __x.size()) __n = __x.size();
        },
        __c);
    return __n;
  }
#endif
};

#if __cpp_deduction_guides >= 201606L

template <class... _Args> zip(_Args &&...) -> zip<_Args...>;

// For gcc version < 10
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80438
template <class _Tp, class... _Args>
zip(_Tp &&, _Args &&...) -> zip<_Tp, _Args...>;

template <class... _Args>
zip(std::initializer_list<_Args>...) -> zip<std::initializer_list<_Args>...>;

#endif

}  // namespace workspace

namespace std {

template <size_t _Nm, class _Tuple>
struct tuple_element<_Nm, workspace::zipped<_Tuple>> {
  using type = remove_reference_t<
      typename iterator_traits<tuple_element_t<_Nm, _Tuple>>::reference>;
};

template <class _Tuple>
struct tuple_size<workspace::zipped<_Tuple>> : tuple_size<_Tuple> {};

}  // namespace std
#line 7 "test/library-checker/number_of_substrings.test.cpp"

int main() {
  std::string s;
  std::cin >> s;
  workspace::suffix_array sa(s);
  long long ans = 0;
  for (auto &&[x, y] : workspace::zip(sa, sa.lcp_array())) {
    ans += s.size() - x - y;
  }
  printf("%lld\n", ans);
}

Back to top page