コンテンツにスキップ

競プロキャンプ2026関西 J - Substring Query

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
J - Substring Query

英小文字からなる文字列 SS が与えられます。QQ 個のクエリで文字列 TiT_i が与えられるので、SS と TiT_i の両方の部分文字列である空でない文字列のうち、最長のものの長さを答える問題です(なければ 00)。制約は 1≤∣S∣≤20001 \le |S| \le 2000、1≤Q≤2×1051 \le Q \le 2 \times 10^5、∑∣Ti∣≤106\sum |T_i| \le 10^6 です。

TT の各位置 jj について、TT の jj 文字目で終わる文字列のうち SS の部分文字列であるものの最長の長さを ℓj\ell_j とします。共通の部分文字列はどれも TT のどこかの位置で終わるので、答えは ℓj\ell_j の最大値です。

ℓj\ell_j は、SS の Suffix Automaton を使うと、TT を前から 1 文字ずつ読みながら求められます。Suffix Automaton は SS のすべての部分文字列を受理するオートマトンです。各状態は SS の部分文字列の集まりを表し、状態の数は O(∣S∣)O(|S|) です。

TT の jj 文字目までを読んだとき、長さ ℓj\ell_j の文字列(その位置で終わる、SS の部分文字列である最長の文字列)を表す状態 vv と ℓj\ell_j を持っておきます。次の文字 cc を読むときは、次のようにします。

  • vv から cc で遷移できれば、遷移して長さを 11 増やす。
  • 遷移できなければ、先頭の文字を削って短くする。Suffix Automaton では、これは suffix link をたどることにあたる。遷移できるようになるか初期状態に戻るまでたどってから、遷移を試す。

長さは 1 文字読むごとに高々 11 しか増えないので、suffix link をたどる回数の合計は ∣T∣|T| 以下です。よって、1 つのクエリは O(∣T∣)O(|T|) で処理でき、全体の計算量は O(∣S∣+∑∣Ti∣)O(|S| + \sum |T_i|) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/suffix-automaton.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(Q);
STR(S);
SuffixAutomaton sam(S);
rep(Q) {
STR(T);
print(max(sam.match_lengths(T)));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SuffixAutomaton は Suffix Automaton で、既定では英小文字を扱います。match_lengths(T) は上の ℓj\ell_j を TT の各位置について並べた列を返すので、その最大値を出力しています。

使用ライブラリ:cpp_include@c3d3c0f