最长公共子串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // 特殊情况
        if (str1.length() == 0 || str2.length() == 0) {
            return "-1";
        }

        int len1 = str1.length();
        int len2 = str2.length();
        // 子串要求连续，因此不能简单定义成“str1前i位与str2前j位组成的公共子串最大长度”这种无视连续关系的定义，找不到递推关系
        // 因此，dp[i][j]表示以str1第i个字符和str2第j个字符结尾的最长公共子串长度
        // 初始化-1
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 不用递归尝试了，因为按照这个定义，当字符不相等时，直接赋0，无法进入递归分支
        // 直接双重for循环搞定
        
        // 只需要记录最大长度和str1结尾下标即可，start = end - maxLength
        int maxLength = 0;
        int end = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 公共字符，则根据定义，在dp[i-1][j-1]的基础上+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                // 更新最大值
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    // 注意！end配合substring使用，end是开区间，因此要记录实际下标的后一位，即i-1的后一位i
                    end = i;
                }
            }
        }

        // 截取str1子串并输出
        if (maxLength == 0) {
            // 不存在公共子串，返回"-1"
            return String.valueOf(-1);
        } else {
            // 存在公共子串，返回最大子串
            return str1.substring(end - maxLength, end);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j] == maxLen) {
                    return str1.substring(i - maxLen, i);
                }
            }
        }
        return "";


    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if(str1.equals(str2))return str1;
        int len1=str1.length();
        int len2=str2.length();
        int[][] dp=new int[len1][len2];
        int max=0,start=0,end=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(str1.charAt(i)!=str2.charAt(j)){
                    dp[i][j]=0;
                }else{
                    if(i==0 || j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                }
                if(dp[i][j]>max){
                    max=dp[i][j];
                    start=i;
                    end=j;
                }

            }
        }
        return str2.substring(end-max+1,end+1);
    }
}

public String LCS (String str1, String str2) {
    // write code here
    int index=0 ,len=0;
    int l1=str1.length() ,l2=str2.length();
    int[][] arr=new int[l1+1][l2+1];
    for(int i=0;i<=l1;i++){
        for(int j=0;j<=l2;j++){
            if(i==0 || j==0){
                arr[i][j]=0;
            }else if(str1.charAt(i-1)==str2.charAt(j-1)){
                arr[i][j]=arr[i-1][j-1]+1;
                if(arr[i][j]>len){
                    index=i;
                    len=arr[i][j];
                }
            }
        }
    }
    return str1.substring(index-len ,index);
}

public String LCS (String str1, String str2) {
       int m = str1.length();
       int n =  str2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;
        int endIndex = -1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1]+1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endIndex = i-1;
                    } 
                }
            }
        }
        if (endIndex != -1) {
            return str1.substring(endIndex - maxLen + 1, endIndex + 1);
        } else {
            return "";
        }
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if (str1.length() < 1 || str2.length() < 1) {
            return "";
        }
        // 以i-1结尾的str1和以j-1结尾的str2的最长公共子串长度
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int count = 0;
        int i = 1, j = 1;
        int temp = 0;
        for (i = 1; i < str1.length() + 1; i++) {
            for (j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                // 获取最长公共子串长度count
                if (count < dp[i][j]) {
                    count = dp[i][j];
                    // 记录此时最后一个字符所在位置
                    temp = i - 1;
                }
            }
        }
        // 对其中一个字符串进行切割，即可获得最终答案
        String result = str1.substring(temp - count + 1, temp + 1);
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int n = str1.length();
        int m = str2.length();

        String[][] dp = new String[n+1][m+1];

        String max ="";

        for (int i = 0; i < n+1; i++) {
            dp[i][0] = "";
        }
        for (int j = 0; j < m+1; j++) {
            dp[0][j] = "";
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + str1.charAt(i-1);
                }else {
                    dp[i][j] = "";
                }
                
                if(max.length()<dp[i][j].length()){
                    max = dp[i][j];
                }
 
            }
        }

        return max;
    }
}

public String LCS (String str1, String str2) {
        //连续的，最长，公共子串
        int m=str1.length();
        int n=str2.length();
        int[][] dp=new int[m+1][n+1];
        int maxLen=0;
        int maxEnd=0;
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;//寻找共同长度的子串
                    //在这里更新结果集
                    if(maxLen<dp[i][j]){
                        maxLen=dp[i][j];
                        maxEnd=i-1;//因为(i-1)等于(j-1)
                    }
                }else{
                    dp[i][j]=0;
                }
            }
        }
        return str1.substring(maxEnd-maxLen+1,maxEnd+1);
    }

public class Solution {
    private static final String EMPTY = "";
    public String LCS (String str1, String str2) {
        int sLen1 = str1.length();
        int sLen2 = str2.length();
        // dp[i][j]是包含字符str1[i-1]和字符str2[j-1]的最长子串
        String[][] dp = new String[sLen1 + 1][sLen2 + 1];
        for (int i = 0; i <= sLen1; i++) {
            dp[i][0] = EMPTY;
        }
        for (int j = 0; j <= sLen2; j++) {
            dp[0][j] = EMPTY;
        }
        // 保存最后的结果，在刷dp的时候更新ans
        String ans = EMPTY;
        for (int i = 1; i <= sLen1; i++) {
            for (int j = 1; j <= sLen2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + str1.charAt(i - 1);
                    // 找到更大的结果了
                    if (dp[i][j].length() > ans.length()) {
                        ans = dp[i][j];
                    }
                } else {
                    dp[i][j] = EMPTY;
                }
            }
        }
        return ans;
    }
}

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        //最长相同字符的长度
       int maxLength=0;
       //str1最长相同字符的最后一个字符的索引位置
       int maxLastIndex=0;
       //dp[i][j]表示在str1中以i为结尾和在str2中以j为结尾的最长字串的长度
       int dp[][]=new int[str1.length()+1][str2.length()+1];
        for(int i=0;i<str1.length();i++){
            for(int j=0;j<str2.length();j++){
                //如果相等，那么dp[i+1][j+1]的长度会+1
                if(str1.charAt(i)==str2.charAt(j)){
                    dp[i+1][j+1]=dp[i][j]+1;
                    //维护maxLength和maxLastIndex，在有更长的字串的时候更新其数值
                    if(dp[i+1][j+1]>maxLength){
                        maxLength=dp[i+1][j+1];
                        maxLastIndex=i;
                    }
                //如果不相等说明长度为0
                }else{
                    dp[i+1][j+1]=0;
                }
            }
        }
        // 根据维护的maxLength和maxLastIndex就可以找出其最长字符串
       return str1.substring(maxLastIndex-maxLength+1,maxLastIndex+1);
    }
}

    public String LCS (String str1, String str2) {
        String maxStr="";
        for (int i = 0; i < str1.length(); i++)
            for (int j = 0; j < str2.length(); j++) {
                int x=i;
                int y=j;
                StringBuilder sb=new StringBuilder();
                while (x<str1.length()&&y<str2.length()&&str1.charAt(x)==str2.charAt(y)){
                    sb.append(str1.charAt(x));
                    x++;
                    y++;
                }
                if (maxStr.length()<sb.length())
                    maxStr=sb.toString();
            }
        return maxStr;
    }

public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // 初始化表格，str2位于纵向，str1位于横向
        int[][] table = new int[str2.length() + 1][str1.length() + 1];
        // 当两个字符相等时，用于保存最大子串长度
        int maxSize = 0;
        // 当两个字符相等时，用于记录当前str2字符串的索引是多少。 因为填表顺序，str2为纵向，所以这里结果以str2为寻找点
        int _s2Index = 0;

        // 保存循环中，遍历到两个字符串的字符
        char s1CH,s2CH;
        // 外层循环s2的索引
        int s2Index = 0;
        while (s2Index < str2.length()){
            // 保存当前遍历的str2对应索引字符
            s2CH = str2.charAt(s2Index);

            for (int i = 0; i < str1.length(); i++) {
                // 保存当前遍历的str1对应索引字符
                s1CH = str1.charAt(i);

                // 两个字符相等时
                if(s1CH == s2CH){
                    // 其实表格中第一行和第一列都是0，作为辅助单元。所以实际上每次往表格中插入值时都是行索引 + 1 ，列索引 + 1
                    // 如果相等: 就取左斜方单元格的值进行判断, 第一次循环时，左斜方位于辅助单元, 值是0
                    //   将当前要往表格插入位置table[s2Index+1][i+1] = 左斜方单元格的值 + 1
                    table[s2Index+1][i+1] = table[s2Index][i] + 1;

                    // 如果当前单元格的长度大于maxSize长度，
                    if(table[s2Index+1][i+1] > maxSize){
                        // 则将maxSize 改为当前单元格的长度值
                        maxSize = table[s2Index+1][i+1];
                        // 并记录当前字符相等的 str2位于哪个索引位置
                        _s2Index = s2Index;
                    }
                }
                // 两个字符不相等时，则直接将当前单元格置为0， 表格初始化时默认就是0，所以这里else省略
            }

            s2Index++;
        }

        // 因为遍历时索引从0开始，所以_s2Index应该指向最长子串的最后一个字符之后的索引位置，当它减去maxSize长度时，正好位于子串的首位字符索引
        _s2Index++;

        // 循环结束，maxSize即为最长子串的长度， _s2Index即为最长子串的最后一个字符之后的索引位置
        // 那么截取位置 从 最后一个索引 - 长度开始，到 _s2Index最后一个索引结束
        return str2.substring(_s2Index - maxSize, _s2Index);
    }
}

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        String ret = null;
        int maxlength = 0, x = 0;
        int l1 = str1.length(), l2 = str2.length();
        int[][] matrix = new int[l1][l2];
        for (int i=0; i<l1; i++) {
            for (int j=0; j<l2; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    if (i==0 || j ==0) {
                        matrix[i][j] = 1;
                    } else {
                        matrix[i][j] = matrix[i-1][j-1] + 1;
                    }
                }
                if (maxlength < matrix[i][j]) {
                    x = i;
                    maxlength = matrix[i][j];
                }
            }
        }
        x = x + 1;
        ret = str1.substring(x-maxlength, x);
        return ret;
    }
}

package chaochao.Niuke.dynamicprpgrammer;

import java.util.Arrays;

public class BM66 {

    /**
     * 描述
     * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
     * 题目保证str1和str2的最长公共子串存在且唯一。
     * <p>
     * 数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
     * 要求： 空间复杂度 O(n^2)O(n
     * 2
     * )，时间复杂度 O(n^2)O(n
     * 2
     * )
     * 示例1
     * 输入：
     * "1AB2345CD","12345EF"
     * 复制
     * 返回值：
     * "2345"
     *
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(LCS("1356", "B1356A"));


    }

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


        int s1Length = s1.length() + 1;
        int s2Length = s2.length() + 1;

        //创建字符串矩阵,存储子字符序列
        String[][] result = new String[s1Length][s2Length];


        //将第0列和第0行置空,构造初始数据(最长公共子序列的初始值)
        Arrays.fill(result[0], "");
        for (int i = 0; i < s1Length; i++) {
            result[i][0] = "";
        }
        //填充字符串矩阵
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 1; i < s1Length; i++) {
            for (int j = 1; j < s2Length; j++) {
                //条件1.如果相同,则是子字符序列拼接
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {//减1的原因是矩阵中的0位置外置的,字符串的0位实际存在
                    result[i][j] = result[i - 1][j - 1] + s1.charAt(i - 1);

                    //条件2.不同,记录当前子序列最长
                    stringBuilder = stringBuilder.length() > result[i][j].length() ? stringBuilder : new StringBuilder(result[i][j]);
                } else {
                    result[i][j] = "";
                }
            }
        }


        return stringBuilder.length()== 0 ? "-1" : stringBuilder.toString();
    }
}