F: Longest Match

Report
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  )
1回のクエリをO(log  )で処理
O( log || +  log 
2 bracadabra
5 cadabra
クエリ文字列の合計を L とすると
2)
9 bra
で間に合う
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

similar documents