競プロキャンプ2026関西 J - Substring Query
- サイト
- MOFE
- コンテスト
- 競プロキャンプ2026関西
- 問題
- J - Substring Query
英小文字からなる文字列 が与えられます。 個のクエリで文字列 が与えられるので、 と の両方の部分文字列である空でない文字列のうち、最長のものの長さを答える問題です(なければ )。制約は 、、 です。
の各位置 について、 の 文字目で終わる文字列のうち の部分文字列であるものの最長の長さを とします。共通の部分文字列はどれも のどこかの位置で終わるので、答えは の最大値です。
は、 の Suffix Automaton を使うと、 を前から 1 文字ずつ読みながら求められます。Suffix Automaton は のすべての部分文字列を受理するオートマトンです。各状態は の部分文字列の集まりを表し、状態の数は です。
の 文字目までを読んだとき、長さ の文字列(その位置で終わる、 の部分文字列である最長の文字列)を表す状態 と を持っておきます。次の文字 を読むときは、次のようにします。
- から で遷移できれば、遷移して長さを 増やす。
- 遷移できなければ、先頭の文字を削って短くする。Suffix Automaton では、これは suffix link をたどることにあたる。遷移できるようになるか初期状態に戻るまでたどってから、遷移を試す。
長さは 1 文字読むごとに高々 しか増えないので、suffix link をたどる回数の合計は 以下です。よって、1 つのクエリは で処理でき、全体の計算量は です。
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) は上の を の各位置について並べた列を返すので、その最大値を出力しています。
使用ライブラリ:cpp_include@c3d3c0f