首页 > 代码库 > Java算法——求出两个字符串的最长公共字符串
Java算法——求出两个字符串的最长公共字符串
问题：有两个字符串str1和str2，求出两个字符串中最长公共字符串。
例如：“acbbsdef”和"abbsced"的最长公共字符串是“bbs”
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中行和列对应的每个点的字符是否相同，是设置这个点为1，否设置这个点为0。
3、通过查找值为1的最长对角线来找到最长公共字符串。
通过上面str1和str2两个字符串,分别得出以行和列组成的一个二维矩阵如下图：
从上图可以看到，str1和str2共有3个公共子串"bbs"，公共子串长度为3。
为了避免后续查找对角线长度的操作：
可以先计算二维矩阵值的时候顺便计算出来当前最长的公共子串的长度；
即：某个二维矩阵元素的值由item[i][j]=1演变为item[i][j]=1 +item[i-1][j-1]。
下面是代码实现
public class MaxStringDemo { public static void main(String[] args) { String aa = "abc123edf"; String bb = "bc123jg"; maxUtil2(aa, bb); System.out.println(maxUtil2(aa, bb)); } public static StringBuilder maxUtil2(String str1, String str2) { //把字符串转成字符数组 char[] arr1 = str1.toCharArray(); char[] arr2 = str2.toCharArray(); // 把两个字符串分别以行和列组成一个二维矩阵 int[][] temp = new int[arr1.length][arr2.length]; // 存储最长公共子串长度 int length = 0; //start表明最长公共子串的起始点，end表明最长公共子串的终止点 int end = 0; int start = 0; ////初始化二维矩阵中的第一行 for (int i = 0; i < arr2.length; i++) { temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0; } //初始化二维矩阵中的第一列 for (int j = 0; j < arr1.length; j++) { temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0; } //嵌套for循环：比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0 for (int i = 1; i < arr1.length; i++) { for (int j = 1; j < arr2.length; j++) { if (arr1[i] == arr2[j]) { temp[i][j] = temp[i - 1][j - 1] + 1; if (temp[i][j] > length) { length = temp[i][j]; end = j; } } else temp[i][j] = 0; } } //求出最长公共子串的起始点 start=end-length+1; StringBuilder sb=new StringBuilder(); //通过查找出值为1的最长对角线就能找到最长公共子串 for (int j = start; j < end+1; j++) { sb.append(arr2[j]); } return sb; }}
到这里，求出两个字符串的最长公共字符串的问题已经解决！
Java算法——求出两个字符串的最长公共字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。