スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

LCS と LPS の関係についてわかったところまで

任意の文字列 s を一つ固定する。
s の longest common subsequence ( 以下 LCS ) と longest palindromic subsequence ( 以下 LPS ) の関係について調べていたけど、すぐに解決できそうになかったので、わかったところまでを記録しておく。

Tags : アルゴリズム

記法

文字列 s, t に対して、

|s| := ( s の長さ )

rev(s) := ( s を反転したもの )

CS(s, t) := ( s と t の common subsequence )

LCS(s, t) := ( s と t の longest common subsequence )

LPS(s) := ( s の longest palindromic subsequence )

CS(s, t), LCS(s, t), LPS(s) は一般には一意に決まらない。
それぞれ、全体の集合を同じ記号で呼ぶこともあるので、文脈から判断すること。

|LCS(s, t)|, |LPS(s)| は一意に定まることに注意。

動機

ICPC 2006年度 模擬地区予選 F問題 : It Prefokery Pio の解説スライド
解法 5 に、s の LPS は s と rev(s) の LCS として求められると書いてある。

ほんとに? 証明は??

LCS を使わない解法

まず、LPS(s) は O(|s|2) 時間の DP で求められる。
これはスライドの解法 4, 6 に相当する。

たとえば
Stanford 大学の講義資料(?)
演算法筆記- Palindrome
が詳しい。

これはこれで自己完結していてよい。

LCS との関係

スライドの解法 5 でも注意されているように、一般に LCS(s, rev(s)) ⊂ LPS(s) の包含は成り立たない。
反例は s = "MWADAMW" で、LCS(s, rev(s)) = "MADAW" ととれるがこれは回文でない。

では、LPS(s) ⊂ LCS(s, rev(s)) であるか?
つまり、うまく LCS(s, rev(s)) を求めれば、それが LPS(s) になっているか?
これを証明したいのだけど、なかなかうまくいかないし、インターネット上にもそれらしい記述が見つからない。

どうやら結果としては正しい。
それも、通常の LCS の経路復元によって得られる文字列は自動的に LPS になるようである。
実際、この方法で、上記の問題 It Prefokery Pio で用意されたすべてのテストケースに対して正しい解を求めることができる。

また、
LPS(s) ⊂ CS(s, rev(s))
はわかっている。
証明も易しい。 ( LPS(s) = rev(LPS(s)) を利用する )
なので、あとは
|LPS(s)| = |LCS(s, rev(s))|
を示せばいい。

参考になるかも知れない web ページを挙げておく。
Longest palindromic subsequence - PEGWiki - ( Lemma 2 の主張はおそらく誤り )
techInterview Discussion - Palindrome Problem
TopCoder Forums

おねがい

何かアイデアを持っている方はぜひ教えてください。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。