最长公共子串（图文版）

最长公共子串（图文版）

PS:串一定是连续的，序列可以是不连续的

时间复杂度O(len1*len2)

问题：求2个字符串的最长公共子串

​​字符串="abcde"，str2="abcde"​​

如果两个串相同，那么矩阵的对角线全都是1。

​​串1是abcdefg，串2是acdaefg​​

为了在求最长公共子串时，使得判断更加简单，我们把上图改成下图。

JavaCode:

public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); char[] str1 = reader.readLine().toCharArray(); char[] str2 = reader.readLine().toCharArray(); int str1len=str1.length; int str2len=str1.length; int [][] dp=new int[100][100]; int maxlen=0,endinx=0; for (int i = 0; i < str1len; i++) { for (int j = 0; j < str2len; j++) { if(str1[i]==str2[i]) { if(i==0||j==0) dp[i][j]=1; // 如果是在行头或列头，表示开始位置，所以赋值为1 第一次出现 else dp[i][j]=dp[i-1][j-1]+1; //第二次出现相同字符 }else { dp[i][j]=0; // 否则就是字符不同，赋值为0 } if(dp[i][j]>maxlen) { maxlen=dp[i][j]; // 获取最长公共子串的最大长度 // 获取串1的最长公共子串最后一个字符的下标 endinx=i; } } } // 输出最长公共子串，注意起点和终点 for(int i=endinx-maxlen+1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。