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

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

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

Common Subsequence(PKU No.1458)

二つの文字列とが与えられて、それらの最長共通部分文字列長を求める。

アルゴリズム

挿入コスト、脱落コスト0、置換コストをKroneckerのδとしたときの最大の編集コストを求めるDPマッチングと同じ。

ここで、挿入、脱落コストが0でなのでなら必ずとなる。従って、なら直ちにとしてもよい。

コード

2項間漸化式になっているので、メモリ節約のためとを使いまわしている。
もうちょいメモリ節約できそうだけどややこしいのでこのくらいでいいか。

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];
	}
}