common

C: COMMON PALINDROMES
原案・解説：保坂
問題概要
• 文字列 S, T の共通の回文を数える
• ただしある回文が S に a 回，T に b 回現れていたら ab
個として数える
• |S|, |T| <= 50,000
解法 (1)
• Suffix Array を使う
• 接尾辞をソートした配列
•
•
•
•
例： "ICPC" の Suffix Array は [ "C", "CPC", "ICPC", "PC" ]
実用的には O(N (log N)2) で構築できる (N は文字列の長さ)
隣接 2 項の最長共通接頭辞を O(N) で求められる
さらに RMQ を用いて任意の 2 項の最長共通接頭辞を求められる
• 構築 O(N log N) / クエリ O(1)
• 構築 O(N) / クエリ O(log N)
• 文字列 S $1 rev(S) $2 T $3 rev(T) に対して Suffix Array を
構築する
• $1, $2, $3 は区切りのための番号が小さな文字
解法 (1)
• 例： ICPC $1 CPCI $2 CPCPC $3 CPCPC
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
S
T
T'
S'
S
T
T'
S'
T
T'
S'
S
S
T
T'
S'
T
T'
C
C
C
CI
CPC
CPC
CPC
CPCI
CPCPC
CPCPC
I
ICPC
PC
PC
PC
PCI
PCPC
PCPC
1
1
1
1
3
3
3
3
5
0
1
0
2
2
2
2
4
解法 (1)
• 長さが奇数 2k - 1の回文について考える
• 長さ偶数のものも同様
• k の大きい順に考えることにする
• 例： S = "...AABACDCABAB..."，k = 4
• Suffix Array 中には，S の接尾辞 "DCAB..." と rev(S) の接尾辞
"DCAB..." として現れる (これらはどちらも回文の中心から始
まっている)
• すなわち，共通接頭辞が k の部分をグループにしておくと，同じ
グループ内に現れる
解法 (1)
• 最長共通接頭辞が k 以上のものをグループにまとめてい
く
• 文字列中の各位置に対して，そこから順方向のものと逆
方向のものが同じグループに入るのがいつかを求めてお
く
• 先ほどの例なら "DCABAB..." と "DCABAA..." が同じグループに
入るのは k = 5 のとき
• すなわち，ある位置を中心とする最長の回文のサイズに対応
• Suffix Array 上で 2 項の最長共通接頭辞を求めればよい
• k が小さくなり条件を満たしたらグループのカウンタを
増やす
解法 (1)
• 管理するもの
• グループごとに，
• S と rev(S) で同じ位置から始まるものの個数 a
• T と rev(T) で同じ位置から始まるものの個数 b
• 積 ab のすべてのグループについての和 X
• ある k の値に対して処理するごとに，X を答えに足す
• (a1, b1), (a2, b2) のグループをまとめるときは，X から
a1b1 + a2b2 を減らし (a1 + a2)(b1 + b2) を増やす
• (a, b) のグループに S のカウンタを増やすときは，X か
ら ab を減らし (a +1)b を増やす
解法 (1)
• 計算量
•
•
•
•
N = |S| + |T|
Suffix Array の構築 O(N2 (log N)2)
RMQ の処理 O(N log N)
長いほうから X を更新していく O(N) くらい (Union-Find を使え
ば少し増える)
• 各ステップがんばれば O(N) ！
• もちろん定数が重いです
解法 (2)
• 概略：短い回文と長い回文にわける
• 境目は √N 程度
• 短い回文は各中心の位置から作る
• 長い回文は「あまりない」のでうまく処理できる
• それぞれの文字列に対して回文とその個数をすべて求め，適
切なハッシュを作って答えを求める
• 32 bit 整数のハッシュを使うと誕生日攻撃で間違いなく衝突します
• O(N √N log N)
参考
• 「各位置を中心とする最大の回文の長さ」は Suffix
Array を使わなくても O(N) で比較的シンプルに求めら
れる
• Manacher のアルゴリズム
• 一部の処理が楽になります
• N 文字の文字列中に現れる回文は高々 N 種類
• 頭の体操になるので知らなかった方は証明を考えてみましょう
• これを使うと簡単な解法になるかも？
結果
•
•
•
•
•
正解 / 提出： 1 / 16
提出チーム： 6
正解チーム： 1
最初の提出： redsign (00:44)
最初の正解： __________ (03:34)

Download Report