読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

最長共通部分列問題、Common Subsequence(PKU No.1458)

最長共通部分列問題(LCS; Longest Common Subsequence)

二つの値の列が与えられて,最長の共通部分列を見つける問題。
部分列は連続している必要はないが,順序は変更してはい。
LCSは一般的に複数ある。

Common Subsequence(PKU No.1458)

二つの文字列 s_1, s_2, \cdots ,s_n t_1, t_2, \cdots ,t_mが与えられて、それらの最長共通部分文字列長を求める。

アルゴリズム

挿入コスト、脱落コスト0、置換コストをKroneckerのδとしたときの最大の編集コストを求めるDPマッチングと同じ O(nm)
 \begin{array}{ll} LCS_{i,0} = 0 && (0\leq i \leq n, j=0) \\ LCS_{0,j} = 0 && (i=0, 1\leq j \leq m) \\ LCS_{i,j} = \max \left\{ \begin{array}{l} LCS_{i-1,j-1} + \delta_{s_i,t_j} \\ LCS_{i,j-1}\\ LCS_{i-1,j} \end{array} \right. && (1\leq i \leq n, 1\leq j\leq m) \end{array}
ここで、挿入、脱落コストが0でなので s_i = t_jなら必ず LCS_{i-1,j-1} + \delta_{s_i,t_j} \geq LCS_{i,j-1}, LCS_{i-1,j} となる。従って、 s_i = t_jなら直ちに LCS_{i,j} = LCS_{i-1,j-1}+1としてもよい。

コード

2項間漸化式になっているので、メモリ節約のため LCS[ pre] [ j] \equiv LCS_{i-1,j} LCS[ cur] [ j ] \equiv LCS_{i,j}を使いまわしている。
もうちょいメモリ節約できそうだけどややこしいのでこのくらいでいいか。

import java.util.*;
public class pku1458 {
	static Scanner stdin;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new pku1458();
	}
	pku1458(){
		while(stdin.hasNext()){
			String s = stdin.next(); s = " " + s;
			String t = stdin.next(); t = " " + t;
			System.out.println( solve(s.toCharArray(), t.toCharArray()) );
		}
	}
	int solve(char[] s, char[] t){
		int[][] LCS = new int[2][t.length];
		int pre = 0, cur = 1;
		Arrays.fill(LCS[pre], 0);
		for(int i=1; i < s.length; ++i){
			LCS[cur][0] = 0;
			for(int j=1; j < t.length; ++j){
				LCS[cur][j] = s[i] == t[j] ? LCS[pre][j-1] + 1 : Math.max(LCS[pre][j], LCS[cur][j-1] );
			}
			cur = (cur + 1) & 1; // cur = (cur + 1) % 2
			pre = (pre + 1) & 1; // pre = (pre + 1) % 2
		}
		return LCS[pre][t.length-1];
	}
}