标签为 [最长公共子串] 的文章

面试指南——最长公共子串问题

题目: 给定两个字符串,求出它们之间最长的相同子字符串的长度。 1234567891011121314/*  * 公共子串需要连续,公共子序列不需要连续  * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0;  * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0;  * 其他位置从左到右,从上到下计算,dp矩阵有以下两种情况:  * a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的,所以dp[i][j]=0;  * b.如 ......