LCS(最长公共字串)算法 java实现 考虑有多个相同的长度的子串

LCS(Longest Common Subsequence) 就是求两个字符串最长公共子串的问题。

比如：

String str1 = new String("adbccadebbca");
String str2 = new String("edabccadece");
str1与str2的公共子串就是bccade.


解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232


　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：


　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
　　1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
　　0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
　　1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

根据此理得到下列程序，考虑了可能会出现相同长度的子串，返回一个list

package com.parser.main;

import java.util.ArrayList;
import java.util.List;

//LCS算法实现 求两个字符串中间最长的公共字符串

public class Ss {

	public static void main(String[] args) {
		Ss ss = new Ss();
		ss.getSameStr("12", "123pdg123");		                                                                  
	}
	
	public List<String> getSameStr(String str1, String str2){
		char[] arrchar1 = str1.toCharArray();
		char[] arrchar2 = str2.toCharArray();
		int[][] arr = new int[arrchar1.length][arrchar2.length];
		int len = arrchar1.length < arrchar2.length ? arrchar1.length:arrchar2.length;
		int maxarr[] = new int[len];
		int maxindex[] = new int[len];
		for(int i = 0; i < arrchar1.length ; i++){
			for(int j = 0; j < arrchar2.length ; j++){
				if(arrchar2[j] == arrchar1[i]){
					if(i == 0 || j == 0){
						arr[i][j] = 1;
						if(maxarr[0] < 1){
							maxarr[0] = 1;
							maxindex[0] = i;
						}
					}else{
						arr[i][j] = arr[i-1][j-1] + 1;
						//如果当前求出的子串长度大于了maxarr中第一个数值 则清空maxarr数值 全部置0 同时替换第一个最大值
						if(maxarr[0] < arr[i][j]){
							maxarr[0] = arr[i][j];
							maxindex[0] = i;
							for(int num = 1; num < maxarr.length; num++){
								if(maxarr[num] == 0){
									break;
								}else{
									maxarr[num] = 0;
									maxindex[num] = 0;
								}
							}
						}else if (maxarr[0] == arr[i][j]){
							//如果当前求出的子串长度跟maxarr中第一个一致 则保留
							int num = 0;
							for(int max : maxarr){
								if(max == 0){
									maxarr[num] = arr[i][j];
									maxindex[num] = i;
									break;
								}
								num++;
							}
						}
					}
				}else{
					arr[i][j] = 0;
				}
			}
		}
		for(int i = 0;i < arr.length ; i++){
			for(int j = 0;j < arr[i].length;j++){
				System.out.print("   " + arr[i][j]);
			}
			System.out.println("");
		}
		
		List<String> list = new ArrayList<String>();
		
		
		for(int i = 0; i< maxarr.length ;i++){
			if(maxarr[i] == 0){
				break;
			}
			int num = maxindex[i] - (maxarr[i] -1);
			String str = "";
			for(int k = 0;k<maxarr[i];k++){
				char tempchar = arrchar1[num];
				str += String.valueOf(tempchar);
				num++;
			}
			System.out.println(str);
			list.add(str);
		}
				
		return list;
	}
}

output：
   1   0   0   0   0   0   1   0   0
   0   2   0   0   0   0   0   2   0
12
12