LCS最长公共子序列

例如 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;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/82389398