1458(LCS)

昨日の反省をふまえてLCSを色々作ってみた。昨日のfox(笑)のid:awakia-n案も実装してみた。結構綺麗に出来たと思う。O(NM)。合ってるか分からんけど。

考え方。LCSの性質上、文字列x, yの順序を逆転した物をx', y'としたとき、lcs(x, y)とlcs(x', y')の内容は変わっても長さは変わらない。なので、[xi, 末尾]、[yi, 末尾]の区間のLCSの長さはx'とy'に置き換えて考えると[0, xi']、[0, yi']の区間のLCSと同じになる。よって、予め通常の文字列とreverseした文字列でLCSのテーブルを作って置く事でプログラムが綺麗になるかもという感じ。