问题：有两个字符串str和str2。 求出两个字符串中最长的公共子列的长度。
例如，如果str=acbcbcef、str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串的长度为5。
算法思路： 1、将两个字符串分别用行和列组成一个二维矩阵。
2、比较二维矩阵中各点对应的矩阵字符中是否相等，如果相等，则将值设定为1，否则设定为0。
3、通过找到值为1的最长对角线可以找到最长公共子串。
为上面的两个字符串得到的二维矩阵如下。
如上图所示，str1和str2共有5个公共子列，但最长的公共子列的长度为5。
为了进一步优化算法效率，在重新计算某个二维矩阵的值时，顺便说明当前最长的公共子串的长度，即某个二维矩阵元素的值从dp[i][j]=1到dp[i][j]=1 dp[i-1][j-1] 修改后的二维矩阵如下。
状态转移方程：
java代码的实现如下。 包DP； public class LCS _1{ publicstaticvoidmain (string [ ] args ) { LCS_1 lcs=new LCS_1； stringstr=LCS.getLSC(acbcbcef，) abcbced )； system.out.println(str； }privatestringgetLSC(stringa，String B ) { int [ ] [ ] DP=new int [ b.length ] ] [ a.length ] ]； int end_index=0； int maxLength=0； for(intI=0； i A.length (； I ) for(intj=0； j B.length (； j ) if(b.charat(j )=a.charat ) ) if ) I==0|||j==0) ) { dp[i][j]=1； } else { dp[i][j]=dp[i - 1][j - 1] 1； (if ) DP[I][j]maxlength ) { maxLength=dp[i][j]； end_index=j； } } system.out.print ln (' maxlength=' maxlength )； system.out.println (' end _ index=' end _ index )； end_index =1； returnb.substring (end_index-maxlength，end _ index )； }转载连接： https://blog.csdn.net/QQ _ 25800311/article/details/81607168