问题描述

如题。

例：输入两个字符串 str1="1AB234",str2="1234EF" ，应输出最长公共子串"234".

解题思路

状态表示

dp[i][j]表示把str1[I]和str2[j]作为公共子串的最后一个字符，最长公共子串的长度。

最终，找到dp数组中的最大值及其位置，则可计算并获得最长子串。

状态转移方程

dp[i][j]=dp[i-1][j-1]+1 ,(str[i]==str[j])

dp[i][j]=0,(str[I]!=str[j])

对空间进行压缩，空间复杂度由O(M*N)压缩至O(1)

• 由于dp[i][j]只依赖于dp[i-1][j-1]，所以可以将空间压缩至O(1).
• 斜线起始点由右上角开始，向左向下。一条斜线中，从左上，至右下遍历。
• 代码中,len即为dp[i][j]，表示状态。
• 此外，维护最大子串长度及对应的结尾位置两个变量即可。

代码(空间复杂度O(1)版)

public class Main {

	public static void main(String[] args) {

		String s1="1AB2345CD";

		String s2="12345EF";

		String subStr=LCST(s1,s2);

		System.out.println(subStr);

	}

	public static String LCST(String s1,String s2) {

		if(s1==null||s2==null||s1.length()==0||s2.length()==0) {

			return "";

		}

		int longestLen=0;

		int longestPos=-1;

		int rows=s1.length();

		int cols=s2.length();

		int rBeg=0;

		int cBeg=cols-1;

		while(rBeg<rows) {

			//初始化斜线起点位置

			int i=rBeg;

			int j=cBeg;

			int len=0;//

			//一条斜线

			while(j<cols&&i<rows) {

				if(s1.charAt(i)!=s2.charAt(j)) {

					len=0;

				}

				else {

					len+=1;

				}

				if(len>longestLen) {//

					longestLen=len;

					longestPos=j;

				}

				++j;

				++i;

			}

			//移动斜线起点位置

			if(cBeg>0) {

				--cBeg;

			}

			else {

				++rBeg;

			}

		}

		return s2.substring(longestPos+1-longestLen,longestPos+1);

	}

}