例如 b c d d e和 a c e e d e的公共子串为c d e。
如果使用暴力，复杂度太高会直接超时。就需要使用动态规划
dp[i][j]表示a串第i个结尾，b串第j个结尾的最长公共子串的数量。- 首先分析i,j的情况
1.如果a[i]==b[j],因为两个元素都在最末尾的位置。所以一定可以匹配成功。换句话说，这个位置的邻居不可能大于他（最多相等）.所以这个时候就是dp[i][j]=dp[i-1][j-1] +1;像例子就是类似 求dp（b c d d和a c e e d e）两个末尾加上e，所以结果就出来了。
2.如果a[i]!=b[j],这样考虑的角度有两个，这样就要考虑继承的关系，当然要考虑继承大的，你不知道a串的最后一个和b串倒数第二个的dp大还是a串的倒数第二个和b串的最后一个那个大，（也可能相等）比如 a b c和e c q这两个串肯定选择继承（a,b,c）和(e,c)串的dp值而不会选择继承（a,b）和（e,c,q）的dp值。
这样代码就好些了，附上Java代码（数组申请大以为从1开始操作）
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; public class testD { public static void main(String[] args) throws IOException { // TODO 自动生成的方法存根 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out)); while(in.nextToken()!=StreamTokenizer.TT_EOF) { String s1=in.sval; in.nextToken();String s2=in.sval; char a1[]=s1.toCharArray(); char a2[]=s2.toCharArray(); // int index1=0;int index2=0; int dp[][]=new int[s1.length()+1][s2.length()+1]; for(int i=1;i<s1.length()+1;i++) { for(int j=1;j<s2.length()+1;j++) { if(a1[i-1]==a2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; } else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } out.println(dp[a1.length][a2.length]);out.flush(); } } private static int max(int i, int j) { // TODO 自动生成的方法存根 return i>j?i:j; } }
