Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 305 InterleavePal

|  SRM 305 InterleavePal - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 305 InterleavePal - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6435


public class InterleavePal {

	String _s, _t;
	int _max;
	
	boolean[][][][] memo;
	
	public void dfs(int ss, int se, int ts, int te) {
		int len = (se - ss) + (te - ts);
		if (_max < len) {
			_max = len;
		}
		
		if (memo[ss][se][ts][te]) {
			return;
		}
		
		if (ss >= 1) {
			if (se < _s.length() && _s.charAt(ss-1) == _s.charAt(se)) {
				dfs(ss-1, se+1, ts, te);
			}
			if (te < _t.length() && _s.charAt(ss-1) == _t.charAt(te)) {
				dfs(ss-1, se, ts, te+1);
			}
		}

		if (ts >= 1) {
			if (se < _s.length() && _t.charAt(ts-1) == _s.charAt(se)) {
				dfs(ss, se+1, ts-1, te);
			}
			if (te < _t.length() && _t.charAt(ts-1) == _t.charAt(te)) {
				dfs(ss, se, ts-1, te+1);
			}
		}
		memo[ss][se][ts][te] = true;
	}

	public int longestPal(String s, String t) {
		_s = s;
		_t = t;
		memo = new boolean[51][51][51][51];
		for (int ss = 0 ; ss <= _s.length() ; ss++) {
			for (int tt = 0 ; tt <= _t.length() ; tt++) {
				dfs(ss, ss, tt, tt);
				if (ss != _s.length()) {
					dfs(ss, ss+1, tt, tt);
				}
				if (tt != _t.length()) {
					dfs(ss, ss, tt, tt+1);
				}
			}			
		}
		return _max;
	}
}