F: Longest Match 原案: 鮫島 担当: 鮫島，安藤 問題概要 文字列 𝑆 と，𝑚 個のクエリが与えられる 各クエリについて，文字列 𝑥𝑖 , 𝑦𝑖 が与えられる 𝑆の部分文字列で，𝑥𝑖 で始まり𝑦𝑖 で終わるものの中 で，最長の文字列の長さは？ そのような部分文字列がない場合，0を出力 制約 𝑆 ≤ 2 ∗ 105 , 𝑚 ≤ 105 , 𝑥𝑖 + 𝑦𝑖 ≤ 2 ∗ 105 例1 S = “abracadabra” クエリ 𝑥𝑖 = “ab”, 𝑦𝑖 = “a” “ab”から始まって，”a”で終わる最長の部分文字列 “abracadabra” が最長なので，11が答え 例2 S = “abracadabra” クエリ 𝑥𝑖 = “b”, 𝑦𝑖 = “c” “b”から始まって，”c”で終わる最長の部分文字列 “brac” が最長なので，4が答え 例3 S = “abracadabra” クエリ 𝑥𝑖 = “z”, 𝑦𝑖 = “z” “z”から始まって，”z”で終わる最長の部分文字列 そのような部分文字列は存在しないので，0が答え 最長になる部分文字列？ 𝑆の中で 𝑥𝑖 が最初に見つかる位置 𝑎𝑖 𝑦𝑖 が最後に見つかる位置 𝑏𝑖 が求められれば，最長の部分文字列も求められそう 𝑥𝑖 , 𝑦𝑖 に対してそれぞれ独立な問題を解けばよい 𝑆 = “abracadabra” 𝑥𝑖 = “b”, 𝑦𝑖 = “c” なら 𝑥𝑖 が最初に見つかる位置は， “abracadabra” • 𝑎𝑖 = 1 • “abracadabra”, 𝑎𝑖 = 8 は最初じゃないのでだめ 𝑦𝑖 が最後に見つかる位置は， “abracadabra” • 𝑏𝑖 = 4 よって，最長の部分文字列の長さは (𝑎𝑖 – 𝑏𝑖 ) + 1 = 4 愚直な解法 文字列 𝑆 から文字列 𝑇 が最初に見つかる位置を求める (文字列𝑆, 𝑇を反転すれば，最後にみつかる位置も求められる) 考えられるアルゴリズム brute-force 1クエリ当たり O(|S||T|) 間に合わない KMP法,BM法 𝑇 ≤ 𝑆 なので，1クエリ当たり O(|S|) クエリ数が膨大なので，これでも間に合わない 解法1 suffix array(接尾辞配列) を使う 接尾辞 : 後ろについている文字列 接尾辞配列 長さ 𝑆 n の文字列 𝑆 について 0: 𝑛 , 𝑆 1: 𝑛 , 𝑆 2: 𝑛 … 𝑆[𝑛 − 1: 𝑛]を作成 11 a 8 abra 1 abracadabra 4 acadabra 6 adabra 𝑆 𝑎: 𝑏 = 𝑆 𝑎 + 𝑆 𝑎 + 1 + … + 𝑆[𝑏 − 1] 9 bra 要するに部分文字列 2 bracadabra これらを辞書順にsortしたもの 開始位置 接尾辞 構築方法は色々 蟻本ではO( 𝑆 log S 5 cadabra 7 dabra 10 ra 2 ) が紹介 3 racadbra 解法1 何が嬉しいのか suffix array を構築すると，文字列𝑇が 現れる位置を O( T log |𝑆|) で求められる！ suffix array に対して2分探索 2分探索部分でバグらせない様に注意 開始位置 接尾辞 11 a 8 abra 1 abracadabra 4 acadabra 6 adabra 例) 𝑇 = “ab“ の時 右の表のオレンジの部分が， ”ab”の見つかる場所となる 9 bra 2 bracadabra 5 cadabra 7 dabra 10 ra 3 racadbra 解法1 オレンジの部分で，最小の開始位置を求めたい segment tree を使う 開始位置 接尾辞 11 a 構築はO(|𝑆|) 8 abra sparse tableでもOK 1 abracadabra 4 acadabra メモリ上限に注意 構築は 6 adabra O( 𝑆 log 𝑆 ) 9 bra 1回のクエリをO(log 𝑆 )で処理 5 cadabra クエリ文字列の合計を L とすると O(𝐿 log |𝑆| + 𝑆 log 𝑆 2) 2 bracadabra で間に合う 7 dabra 10 ra 3 racadbra 解法2 Aho-Corasickを使う 非想定解でした クエリ文字列を先読みし，検索パターンとして Aho-Corasickを構築する 作成したtrie木上で，文字列|𝑆|を探索する 最初にクエリ文字列の終端と一致したindexを保存 クエリ文字列の合計を L とすると 構築 : O(𝐿) , クエリ処理 : O(𝐿 + 𝑆 ) 所感 そこそこバグらせている人が多かった suffix array に対する2分探索がバグりやすい 想像以上のsubmit,AC 夏合宿に来るレベルの人には典型だった？ ”abracadabra”を見てsuffix arrayを考えた人も ジャッジ解 鮫島: 142行 3141bytes ヘッダを除く 安藤: 210行 5231bytes Results FA: Navi (52:56) 25ACs, 28 trying teams, 66 submissions
© Copyright 2025 ExpyDoc
