バグを発見しました~

[981377660LMT]

https://maspypy.github.io/library/string/longest_common_substring.hpp

#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;
}

少し調整しました (cppは苦手で擬似コード)

// swap追加
i1, i2 := sa[i], sa[i+1]
if i1 > i2 {
  i1, i2 = i2, i1
}
a := i1;
b := i2 - len(s) - 1;

[maspypy]

修正しました、ありがとうございます！

e3ca97d