[問題案] Longest Common Substring

[maspypy]

概要

文字列 S, T の最長共通部分文字列を出力。subsequence じゃなくて substring の方。 長さ 0 ならば

0

正の長さ n ならば S[l_1,r_1) と T[l_2,r_2) として

n
l_1 r_1 l_2 r_2

を出力

制約

• $|S|, |T| \leq 5\times 10^5$
• 英小文字

解法

• suffix array + lcp で線形時間でできる。
  • S + dummy文字 + T の suffix array を作って、隣接する S, T の substring の lcp を計算すればよい
  • アリ本にある。p.340
  • アリ本の出典は、POJ 2217 らしい。
• S の suffix automaton を作るとかでも良さそう
  • https://yosupo.hatenablog.com/entry/2021/01/31/160215
• S+T の suffix tree を作っても良さそう

[maspypy]

作業者募集です。

[maspypy]

やります