LCS
Longest-common subsequence(最長共通部分列)
共通する部分列で最長のものを求める。
計算量は$ O(NM)(それぞれ長さが$ Nと$ Mの列のLCM)
列A, B のLCSを求める。
前処理:A, Bの先頭にゼロ接頭辞(A, B内になければOK。#とか)を追加。
$ DP\lbrack i \rbrack \lbrack j \rbrack =列Aの$ i文字目、列Bの$ j文字目まで見たときのLCSの長さ
と定義。
DPテーブルはサイズ$ |A|*|B|、$ DP\lbrack 0 \rbrack \lbrack 0 \rbrack = 0で初期化。
遷移は貰うDPで
$ DP\lbrack i \rbrack \lbrack j \rbrack = \left\{\begin{array}{ll}0 & (i = 0 \; or \; j = 0)\\ max(DP\lbrack i-1 \rbrack \lbrack j \rbrack, DP\lbrack i \rbrack \lbrack j-1 \rbrack) & (A_i \neq B_j)\\DP\lbrack i-1 \rbrack \lbrack j-1 \rbrack + 1 & (A_i = B_j)\end{array}\right.