longest common substring java_最长公共子串算法(Longest Common Substring)

川长思鸟来 2022-11-08 09:18 48阅读 0赞

给两个字符串，求两个字符串的最长子串

(例如：“abc”“xyz”的最长子串为空字符串，“abcde”和“bcde”的最长子串为“bcde”)

解题思路：

把两个字符串分成一个行列的二维矩阵

比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。

通过查找出值为1的最长对角线就能找到最长公共子串。

![1620461838.png][]

从图中我们可以看到，等于1的那个对角线就是我们要求的最长公共子串，同时我们还可以再优化一下：

刚才我们说“比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。” ，那么我们并不需要一直等于1，即：两个值相等时(a\[i\]b\[j\])，我们判断对角线前一个值是否相等(a\[i-1\]b\[j-1\]), 如果相等，那么我们只需要加上前一个的值即可。

![921439007.png][]

我们可以通过一个二维数组实现：

int\[\]\[\] arr = new int \[a.length()\]\[b.length()\];

if (a.substring(i,i+1).equals(b.substring(j,j+1)))\{

arr\[i\]\[j\] = 1+ arr\[i-1\]\[j-1\] ;

\}

完整代码为：

public class Lcs \{

public static String lCs(String a,String b)\{

int\[\]\[\] arr = new int \[a.length()\]\[b.length()\];

int leng = 0;

int index = 0;

for (int i=0;i

for (int j=0;j

if (a.substring(i,i+1).equals(b.substring(j,j+1)))\{

if (i>0 && j>0)\{

arr\[i\]\[j\] = 1+ arr\[i-1\]\[j-1\] ;

\}else\{

arr\[i\]\[j\] = 1;

\}

\}else \{

arr\[i\]\[j\] = 0;

\}

if (arr\[i\]\[j\]>leng)\{

leng=arr\[i\]\[j\];

index = i ;

\}

\}

\}

return a.substring(index-leng+1,index+1);

\}

public static void main(String\[\] args) \{

System.out.println(Lcs.lCs("abcdefghij","asdabchij"));

\}

\}

[1620461838.png]: https://www.isdxh.com/usr/uploads/2019/04/1620461838.png
[921439007.png]: https://www.isdxh.com/usr/uploads/2019/04/921439007.png

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode: 14.Longest Common（最长公共起始串）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

灰太狼/ 2023年07月05日 10:21/ 0 赞/ 16 阅读

相关 Longest Common Subsequence（C++最长公共子序列）

解题思路：（1）动态规划 class Solution { public: int longestCommonSubsequence(st

谁践踏了优雅/ 2023年01月17日 04:57/ 0 赞/ 200 阅读

相关算法：最长公共前缀（longest-common-prefix）。

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 `""`。示例 > 输入: ["flower","flow","fligh

叁歲伎倆/ 2022年11月26日 11:56/ 0 赞/ 154 阅读

相关 longest common substring java_最长公共子串算法(Longest Common Substring)

给两个字符串，求两个字符串的最长子串 (例如：“abc”“xyz”的最长子串为空字符串，“abcde”和“bcde”的最长子串为“bcde”) 解题思路：把两个字符串分

川长思鸟来/ 2022年11月08日 09:18/ 0 赞/ 49 阅读

相关算法: 最长公共子串1143. Longest Common Subsequence

[1143. Longest Common Subsequence][] Given two strings text1 and text2, return the le

痛定思痛。/ 2022年09月17日 03:28/ 0 赞/ 158 阅读

相关 JavaScript实现longest Common Substring最长公共子串算法（附完整源码）

JavaScript实现longest Common Substring最长公共子串算法（附完整源码） longestCommonSubstring.js完整源代码

川长思鸟来/ 2022年09月07日 12:29/ 0 赞/ 152 阅读

相关 SPOJ Longest Common Substring II

求十个串的最长连续公共子串。第一个串建立自动机。用其它每个串在自动机上跑一遍，记录每个状态上能匹配的最长长度。然后求每个状态匹配长度的最小值。注意每个状态

素颜马尾好姑娘i/ 2022年08月04日 04:26/ 0 赞/ 138 阅读

相关最长回文子串（Longest Palindromic Substring）

Leetcode 5. Longest Palindromic Substring Description Given a string s, find the longe

红太狼/ 2022年06月09日 04:26/ 0 赞/ 189 阅读

相关 LCS(longest common subsequence)（最长公共子序列）算法（模板）

看了几分写的相当好的博客：介绍：[程序员编程艺术第十一章：最长公共子序列(LCS)问题][LCS] 表格展示：[LCS算法（最长公共子序列问题）][LCS 1] 代码：

谁践踏了优雅/ 2022年05月11日 14:54/ 0 赞/ 181 阅读

相关 POJ 2774 Long Long Message+Hdu 1403 Longest Common Substring (后缀数组最长公共子串)

两题虽然描述不同，但模型完全一样，代码也一样…… 题意：求给出的两个字符串的最长公共子串，注意和用DP做的LCS(最长公共子序列)不同，子串要求连续思路：将两串拼接起来，

旧城等待，/ 2021年11月16日 10:22/ 0 赞/ 210 阅读