Java——最长公共子串问题LCS

秒速五厘米 2022-06-17 00:07 234阅读 0赞

# Java——最长公共子串问题LCS #

求最长公共子序列（Longest Common Subsequence, LCS）： 如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中， 则字符串一称之为字符串二的子串。 但是并不要求子串（字符串一）的字符必须连续出现在字符串二中。

采用一个二维矩阵来记录中间的结果。比如"abab"和"aba",如果两个字符相等就在矩阵中填1

> > 　　 a b　　a　　b
> 
> > a　　1　　0　　1 0
> 
> > b　　0　　1　　0 1
> 
> > a　　1　　0　　1 0

这样矩阵的斜对角线最长的那个就是最长公共子串“aba"。

为了直接得到矩阵中最长的对角线，可以当要在矩阵填1时让它等于其左上角元素加1：

> >  a b　　a　　b
> 
> > a　　1　　0　　1 0
> 
> > b　　0　　2　　0 2
> 
> > a　　1　　0　　3 0

这样矩阵中的最大元素就是最长公共子串的长度，而它所在的那条对角线就是最长公共子序列。下面是矩阵元素的计算公式：

> > > ![20170411094959652][]

package com.kexin.study2;
    
    public class LCS {
    	public static void main(String[] args) {
    		// 设置字符串长度
    		int sublen1 = 5;
    		int sublen2 = 6;
    		// 随机生成字符串
    		String str1 = "((ad)";
    		String str2 = "(a((d)";
    		//二位数组描述矩阵
    		int[][] c = new int[sublen1 + 1][sublen2 + 1];
    		// 动态规划计算所有子问题
    		for (int i = sublen1 - 1; i >= 0; i--) {
    			for (int j = sublen2 - 1; j >= 0; j--) {
    				if (str1.charAt(i) == str2.charAt(j))
    					c[i][j] = c[i + 1][j + 1] + 1;
    				else
    					c[i][j] = Math.max(c[i + 1][j], c[i][j + 1]);
    			}
    		}
    		System.out.println("str1:" + str1);
    		System.out.println("str2:" + str2);
    		System.out.print("LCS:");
    		int i = 0, j = 0;
    		while (i < sublen1 && j < sublen2) {
    			if (str1.charAt(i) == str2.charAt(j)) {
    				System.out.print(str1.charAt(i));
    				i++;
    				j++;
    			} else if (c[i + 1][j] >= c[i][j + 1])
    				i++;
    			else
    				j++;
    		}
    	}
    }

[20170411094959652]: /images/20220617/5f6aac12a10546a6bd63fc6cd45541d4.png