maspypy / library Goto Github PK

vc<T> dp1 = dp;

#include "string/suffix_array.hpp"

template <typename STRING>
tuple<int, int, int, int> longest_common_substring(STRING& S, STRING& T) {
  int dummy = max<int>(*max_element(all(S)), *max_element(all(T))) + 1;
  STRING ST;
  for (auto&& x: S) ST.push_back(x);
  ST.push_back(dummy);
  for (auto&& x: T) ST.push_back(x);
  Suffix_Array X(ST);
  auto& SA = X.SA;
  auto& LCP = X.LCP;

  tuple<int, int, int, int> res = {0, 0, 0, 0};
  int n = 0;
  FOR(i, len(ST) - 1) {
    if ((SA[i] < len(S)) != (SA[i + 1] < len(S))) {
      if (chmax(n, LCP[i])) {

        //  ここで、SA[i] は s の 部分文字列でない可能性があります。(swap必要)
        //
        int a = SA[i];
        int b = SA[i + 1] - len(S) - 1;
        res = {a, a + n, b, b + n};
      }
    }
  }
  return res;
}

#ifdef FASTIO
template <int mod>
void rd(modint<mod> &x) {
  fastio::rd(x.val);
  assert(0 <= x.val && x.val < mod);
}
template <int mod>
void wt(modint<mod> x) {
  fastio::wt(x.val);
}
#endif

#ifdef FASTIO
template <int mod>
void read(modint<mod> &x) {
  read(x.val);
  assert(0 <= x.val && x.val < mod);
}
template <int mod>
void print(modint<mod> x) {
  print(x.val);
}
#endif