最长公共子串

Python解法

LCS问题就是求两个字符串最长公共子串的问题。

解法:

• 用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。

• 求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。

def find_lcsubstr(s1, s2):
    m = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]  # 生成0矩阵，为方便后续计算，比字符串长度多了一列
    mmax = 0  # 最长匹配的长度
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i + 1][j + 1] = m[i][j] + 1
                mmax = max(mmax, m[i + 1][j + 1])
    return mmax  # 返回最长长度
print(find_lcsubstr(input(), input()))

import java.util.*;
public class Main {
    private static final int MAX = 1005;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s1 = sc.next().toCharArray();
        char[] s2 = sc.next().toCharArray();
        int[] dp = new int[MAX];
        int ans = 0;
        for (int i=0; i!=s1.length; i++) {
            for (int j=s2.length-1; j>=0; j--) {
                if (s1[i] == s2[j]) {
                    dp[j+1] = dp[j] + 1;
                    ans = Math.max(dp[j+1], ans);
                }
                else { dp[j+1] = 0; }
            }
        }
        System.out.println(ans);
    }
}

//动态规划，记录字符串以i,j结尾成功匹配时的最大长度，取所有值中最大
#include<iostream>
#include<string>
using namespace std;

int main() {
    string s1,s2;
    cin>>s1>>s2;
    int dp[s1.length()][s2.length()];
    int maxnum = 0;
    
    for(int i = 0; i < s1.length(); i++) {
        for(int j = 0; j < s2.length(); j++) {
            if(i == 0 || j == 0) {
                dp[i][j] = (s1[i] == s2[j]) ? 1:0;
            }
            else {
                dp[i][j] = (s1[i] == s2[j]) ? dp[i-1][j-1]+1 : 0;
            }
            maxnum = max(maxnum, dp[i][j]);
        }
    }
    cout<<maxnum<<endl;
    
    return 0;
}

String a,b;

int result=0;

int n,m;

Scanner sc=new Scanner(System.in);

a=sc.nextLine();

b=sc.nextLine();

m=a.length();

n=b.length();

int dp[][]=new int[n][m];

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(a.charAt(j)==b.charAt(i)){

dp[i][j]=((i==0)||(j==0))?1:dp[i-1][j-1]+1;

result=Math.max(result,dp[i][j]);

}

}

}

System.out.println(result);

 import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            String str1 = sc.nextLine().trim();
            String str2 = sc.nextLine().trim();
            System.out.println(maxCommonStr(str1, str2));
        sc.close();
    }

    private static int maxCommonStr(String str1, String str2) {
        if (str1 == null || str2 == null) {
            return -1;
        }
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        int lmax = 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][j] = dp[i - 1][j - 1] + 1;
                    if(dp[i][j] > lmax)
                    {
                        lmax = dp[i][j];
                    }

                }
            }
        }
        return lmax;

    }
} 

import java.util.Scanner;

/**
 * Dynamic Programming
 * 
 * State:
 *   dp[i][j]: 表示以s1[i]为结尾的子串和以s2[j]为结尾的子串的最长公共连续子串的长度
 *   
 * Initial State:
 *   dp[i][0] = (s1[i] == s2[0]) ? 1 : 0;  when j == 0
 *   dp[0][j] = (s1[0] == s2[j]) ? 1 : 0;  when i == 0
 *   
 * State Transition:
 *   dp[i][j] = (s1[i] == s2[j]) ? dp[i - 1][j - 1] + 1 : 0;  (i > 0 && j > 0)
 *
 * @author wylu
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            char[] s1 = scanner.nextLine().toCharArray();
            char[] s2 = scanner.nextLine().toCharArray();

            int res = 0;
            int[][] dp = new int[s1.length][s2.length];
            for (int i = 0; i < s1.length; i++) {
                for (int j = 0; j < s2.length; j++) {
                    if (s1[i] == s2[j]) {
                        dp[i][j] = (i == 0 || j == 0) ? 1: dp[i - 1][j - 1] + 1;
                        res = Math.max(res, dp[i][j]);
                    }
                }
            }
            System.out.println(res);
        }
    }
}

	

def longest_com_substring(s1, s2):
    n1, n2 = len(s1), len(s2)
    dp = [[0, ] * n2 for _ in range(n1)]
    # i为s1的下标，j为s2的下标，dp[i][j]表示以s[i],s[j]结尾的最长公共子串的长度
    ans = 0
    # 当j=0的时候
    for i in range(n1):
        if s1[i] == s2[0]:
            dp[i][0] = ans = 1
    # 当i=0的时候
    for j in range(n2):
        if s1[0] == s2[j]:
            dp[0][j] = ans = 1
    # dp[i][j] == dp[i - 1][j - 1]
    for j in range(1, n2):
        for i in range(1, n1):
            if s1[i] == s2[j]:
                p = dp[i - 1][j - 1]
                if p != 0:
                    dp[i][j] = p + 1
                else:
                    dp[i][j] = 1
                ans = dp[i][j] if dp[i][j] > ans else ans
    return ans

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    s1,_:=in.ReadString('\n')
    s2,_:=in.ReadString('\n')
    mat:=make([][]int,len(s1)+1)
    for i,_:=range mat{
        mat[i]=make([]int,len(s2)+1)
    }
    max:=0
    for i:=0;i<len(s1);i++{
        for j:=0;j<len(s2);j++{
            if s1[i]==s2[j]{
                mat[i+1][j+1]=mat[i][j]+1
                if mat[i+1][j+1]>max{
                    max=mat[i+1][j+1]
                }
            }
        }
    }
    fmt.Print(max)
}

#include<string>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main(){
    string a, b;
    getline(cin, a);
    getline(cin, b);
    int n = a.size(), m = b.size();
    vector<int> dp(m+1, 0);
    int res = 0;
    for(int i = 0; i < n; i++){
        for(int j = m-1; j >= 0; j--){
            if(a[i] == b[j]){
                dp[j+1] = max(dp[j+1], dp[j]+1);
                if(dp[j+1] > res) res = dp[j+1];
            }else{
                dp[j+1] = 0;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

方法一：滑动窗口法

从较短字符串开始比较，每次减少一个字符(窗口)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        String shortString = s1.length() >= s2.length() ? s2 : s1;
        String longString = s1.length() >= s2.length() ? s1 : s2;

        int maxlen1 = getMaxSameString(longString, shortString);
        System.out.println(maxlen1);
    }

    // 滑动窗口法
    public static int getMaxSameString(String longString, String shortString){
        if(longString == null || shortString == null){
            return 0;
        }
        int len = shortString.length();
        int maxLen = 0;
        for(int i = 0; i < len; i++){
            // 外层循环控制滑动窗口宽度，每次减少字符
            for(int start = 0, end = len - i; end <= len; start++, end++){
                String subStr = shortString.substring(start, end);
                if(longString.contains(subStr)){
                    maxLen = end - start;
                    return maxLen;
                }
            }
        }
        return maxLen;
    }
}

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int i_max=A.size();
        int j_max=B.size();
        int len=0;
        vector<vector<int> > dp(i_max, vector<int> (j_max, 0));
        //step1:初始化
        for(int i=0;i<i_max;++i){
            if(A[i]==B[0]){
                dp[i][0]=1;
            }
        }
        for(int j=0;j<j_max;++j){
            if(B[j]==A[0]){
                dp[0][j]=1;
            }
        }
        //step2:状态转移
        for(int i=1;i<i_max;++i){
            for(int j=1;j<j_max;++j){
                if(A[i]==B[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                len=max(len, dp[i][j]);

            }
        }
        
        return len;
    }
};

int main(){
    string str1,str2;
    cin>>str1>>str2;
    vector<int> A,B;
    for(int i=0;i<str1.size();++i){
        A.push_back(str1[i]);
    }
    for(int i=0;i<str2.size();++i){
        B.push_back(str2[i]);
    }   
    Solution s;
    int res=s.findLength(A,B);
    cout<<res<<endl;
    return 0;
}

动态规划解法

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
 
using namespace std;
 
int maxSame(string s1, string s2)
{
    int len1 = s1.length();
    int len2 = s2.length();
    vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
    int res = 0, pos = 0;
    for(int i = 1; i <= len1; i++)
    {
        for(int j = 1; j < len2+1; j++)
        {
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            res = max(res, dp[i][j]);
        }
    }
    return res;
}
 
int main()
{
    string str1, str2;
    while(getline(cin, str1)  && getline(cin, str2))
        cout << maxSame(str1, str2) << endl;
 
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        char [] c1 = bf.readLine().toCharArray();
        char [] c2 = bf.readLine().toCharArray();
        soultion(c1,c2);
    }

    public static void soultion(char [] c1,char [] c2){
        int max = 0;
        int [][] dep = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
            for (int j = 0; j < c2.length; j++) {
                if(c1[i]==c2[j]){
                    if(i==0||j==0){
                        dep[i][j] = 1;
                    }else{
                        dep[i][j] = dep[i-1][j-1] + 1;
                    }
                }
                max = Math.max(dep[i][j],max);

            }
        }
        System.out.println(max);
    }

}

Java 代码通过

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      /*  String str1 = "helloword";
        String str2 = "loop";*/
        Scanner s = new Scanner(System.in);
        String str1 = s.nextLine();
        String str2 = s.nextLine();
        //System.out.println(str1.substring(1,2));
         System.out.println(lcsIdnex(str1,str2));
    }
    private static String lcsString(String a,String b){
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int[][] d = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
              if(c1[i]==c2[0]){
                  d[i][0] = 1;
              }
        }
        for (int i = 0; i < c2.length; i++) {
            if(c2[i]==c1[0]){
                d[0][i] = 1;
            }
        }
        int max=-1,index=0;
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if(c1[i]==c2[j]){
                    d[i][j]=d[i-1][j-1]+1;
                    if(max<=d[i][j]){
                        max = d[i][j];
                        index =i;
                    }
                }
            }
        }
        return a.substring(index-max+1, index+1);

    }
    private static int lcsIdnex(String a,String b){
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int[][] d = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
            if(c1[i]==c2[0]){
                d[i][0] = 1;
            }
        }
        for (int i = 0; i < c2.length; i++) {
            if(c2[i]==c1[0]){
                d[0][i] = 1;
            }
        }
        int max=-1,index=0;
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if(c1[i]==c2[j]){
                    d[i][j]=d[i-1][j-1]+1;
                    if(max<=d[i][j]){
                        max = d[i][j];
                        index =i;
                    }
                }
            }
        }
        return max;

    }
}

//暴力解法：
int longcommonSubstring(string s1, string s2)
{
    if (s1.empty() || s2.empty())
        return 0;
    int l1 = s1.size(), l2 = s2.size();
    int res = 0;
    for (int i = 0; i < l1; i++)
    {
        
        for (int j = 0; j < l2; j++)
        {
            int m = i;
            int k = j;
            int len = 0;
            while (s1[m] == s2[k] && m < l1&&k < l2)
            {
                len++;
                m++;
                k++;
            }
            res = max(res, len);
        }
    }
    return res;
}

//DP
int longcommonSubstring(string s1, string s2)
{
    if (s1.empty() || s2.empty())
        return 0;
    int l1 = s1.size(), l2 = s2.size();
    int res = 0;
    vector<vector<int>> DP(l1, vector<int>(l2));
    for (int i = 0; i < l1; i++)
    {
        for (int j = 0; j < l2; j++)
        {
            if (s1[i] == s2[j])
            {
                if (i == 0 || j == 0)
                    DP[i][j] = 1;
                else
                    DP[i][j] = 1 + DP[i - 1][j - 1];
            }
            else
                DP[i][j] = 0;
            res = max(DP[i][j], res);
        }
    }
    return res;
}

//LCS  最长公共子串的问题

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

void findLength(string& str1,string& str2) {
    int size1 = str1.size();
    int size2 = str2.size();
    int res = 0;
    vector<vector<int> > lcs(size1,vector<int>(size2,0));
    for(int i=0;i<size1;i++)
    {
        for(int j=0;j<size2;j++)
        {
            if(str1[i]==str2[j])
            {
                if(i==0||j==0)
                {
                    lcs[i][j]=1;
                }
                else{
                    lcs[i][j]=lcs[i-1][j-1]+1;
                }
            }
             res=max(res,lcs[i][j]);
        }
       
    }
    cout<<res<<endl;
}
 
int main() {
    string str1,str2;
    cin>>str1;
    cin>>str2;
    fun(str1,str2);
    return 0;
}

import java.util.Scanner;

public class Main{
    int maxLen(String stra, String strb){
        if(stra.length() == 0 || strb.length() == 0) return 0;
        if(stra.charAt(0) != strb.charAt(0)){
            int a = maxLen(stra.substring(1),strb);
            int b = maxLen(stra,strb.substring(1));
            return a>b?a:b;
        }else{
            int i = 1;
            int j = 1;
            int count = 1;
            while(i<stra.length() && j<strb.length()){
                if(stra.charAt(i) == strb.charAt(j)){
                    count++;
                    i++;
                    j++;
                }else{
                    break;
                }
            }
            int a = maxLen(stra.substring(i),strb);
            int b = maxLen(stra,strb.substring(j));
            int c = a>b?a:b;
            return c>count?c:count;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Main obj = new Main();
        String stra = sc.nextLine();
        String strb = sc.nextLine();
        System.out.println(obj.maxLen(stra, strb));
        return;
    }
}