输入和输出

• 输入：
  asdfwww
cvcasdfeew
• 输出：
  asdf

动态规划

• 俩种情况

  • 第一种情况
    
    当比较到i=3,j=3时；上面最长的公共子字符串长度为f,长度为1；
    可以使用
    dp[i][j]=1;

  • 第二种情况
    

    当比较到i=5,j=5时；上面最长的公共子字符串长度为gaf,长度为3；长度为3是拿本身的1加上前面的俩个相等的值。
    可以使用
    dp[i][j]=dp[i-1][j-1]+1;

以上俩种情况可以归为一类
首先因为s1字符串的长度是m,s2的字符串的长度是你，所以可以设计一个int[m][n]的二维数组来存储中间的状态，因为出现了以上俩种情况，所以这里在设计二维数组的时候，行和列都加一行和一列，目的是将第一种情况转变成第二种情况。都变成dp[i][j]=dp[i-1][j-1]+1;方便计算（如下图）

import java.util.Scanner;
/**** 从俩个不确定长度的字符串中找出最长公共子串* */
class Test1{public static void main(String[] args){Scanner sc = new Scanner(System.in);String s1 = sc.nextLine();String s2 = sc.nextLine();comMaxLenStr(s1, s2);}public static void comMaxLenStr(String s1,String s2){int m = s1.length();int n = s2.length();// 定义存储状态的数组，（见上面第二种）int[][] dp=new int[m+1][n+1];// 初始化最大长度为0int maxlen=0;// 初始化最大公共字符串的截至位置为-1int endPos=-1;// 双重for循环遍历，一个一个的遍历for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){// 对应字符串位置是否相等，如果相等，二维数组对应的值等于dp[i][j]=dp[i-1][j-1]+1;if(s1.charAt(i-1)==s2.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}// 如果对应位置数组存储的值大于最大公共字符串长度的话，将maxlen替换保存下来,并且记录下来当前s1字符串的最长公共子字符串的截至位置if(maxlen<dp[i][j]){maxlen=dp[i][j];endPos=i;}}}// 如果最长公共子字符串的长度为0，提示没有最长公共字符串if(maxlen==0){System.out.println("没有公共字符串");}else{// 根据最长字符串的截至位置和最大长度，计算出最长公共子字符串并输出System.out.println(s1.substring(endPos-maxlen, endPos));}}}