bluejeans.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;

/**
 * ID:3080
 * DP,最长连续子串
 * @author yhm
 *
 */
public class BlueJeans {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for (int i = 0; i < caseNum; i++) {
			int size = cin.nextInt();
			String[] str = new String[size];
			for (int j = 0; j < size; j++) {
				str[j] = cin.next();
			}
			for (int j = 1; j < size; j++) {
				str[j] = solve(str[j - 1], str[j]);
			}
			if (str[size - 1].length() < 3) {
				System.out.println("no significant commonalities");

			} else {
				System.out.println(str[size - 1]);
			}

		}


	}

	static String solve(String a, String b) {
		int sa = a.length();
		int sb = b.length();
		int[][] m = new int[sa + 1][sb + 1];
		int i = 0, j = 0;

		int max = 0;
		int x = 0, y = 0;
		for (i = 1; i <= sa; i++) {
			for (j = 1; j <= sb; j++) {
				if (a.charAt(i - 1) == b.charAt(j - 1)) {
					m[i][j] = m[i - 1][j - 1] + 1;
					if (max == m[i][j]) {
						String str1 = a.substring(i - max, i);
						String str2 = a.substring(x - max, x);
						if (str1.compareTo(str2) < 0) {
							x = i;
						}
					} else if (max < m[i][j]) {
						x = i;
						max = m[i][j];
					}
				} else {
					m[i][j] = 0;
				}
			}
		}

		String str = a.substring(x - max, x);
		return str;


	}

}