首页 > 试题广场 >

最大公共子串

[编程题]最大公共子串
  • 热度指数:4085 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定两个字符串,请编写代码,输出最长公共子串(Longest Common Substring),是指两个字符串中的最长的公共子串,要求子串一定是连续。

数据范围:输入的两个字符串长度满足

输入描述:
文本格式,2个非空字符串(字母数字组成),2个字符串以","英文逗号分割。


输出描述:
整形,为匹配到的最长子串长度
示例1

输入

bab,caba

输出

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

int main(){
    string s,s1,s2;
    cin>>s;
    int p = s.find(',');
    s1 = s.substr(0,p);
    s2 = s.substr(p+1);
    int Max = 0, m=s1.size(), n=s2.size();
    int dp[m+1][n+1];
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            if(s1[i]==s2[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = 0;
            if(dp[i+1][j+1] > Max)
                Max = dp[i+1][j+1];
        }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-09-10 21:55:36 回复(2)
这题和快手的那个(最长无重子串)如出一辙
a,m = input().split(','),[0,1]
while sum(m) < len(a[1]) + 1:
    m[1 if a[1][m[0]:sum(m)] in a[0] else 0] += 1
print(m[1] - 1)


编辑于 2020-03-19 16:15:43 回复(1)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String[] list = s.split(",");
        String a = list[0];
        String b = list[1];
        int len_a = a.length();
        int len_b = b.length();
        int[][] dp = new int[len_a+1][len_b+1];
        int ans = 0;
        for(int i=1;i<=len_a;++i)
            for(int j=1;j<=len_b;++j){
                if(a.charAt(i-1)==(b.charAt(j-1))){
                     dp[i][j] = dp[i-1][j-1]+1;
                     ans = Math.max(ans,dp[i][j]);
                }
                // 注意此处要求的是连续子串
                else dp[i][j] = 0;
            }
        System.out.println(ans);

    }
}
发表于 2020-07-01 15:46:45 回复(0)
搞清楚最大公共字串和最大公共子序列的区别
字串必须要求连续;子序列不要求连续
经典动态规划
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 5;
int dp[maxn][maxn];

int main() {
    string s; cin>>s;
    int idx = s.find(',');
    string first = s.substr(0, idx), second = s.substr(idx + 1);
	int row = first.length(), col = second.length();
	int res = 0;
    for(int i = 1; i <= row; i++)
        for(int j = 1; j <= col; j++) {
            if(first[i - 1] == second[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
				res = max(res, dp[i][j]);
            } else 
                dp[i][j] = 0;
        }
    cout<<res<<endl;
}
/*
bab,caba
12345678,987567129
*/


编辑于 2019-12-30 11:12:34 回复(0)
#include <bits/stdc++.h>
//从矩阵斜线找最大值
using namespace std;
int main(){
    string str;
    cin>>str;
    int sum=0,pos=str.find(',');
    string s1=str.substr(0,pos);
    string s2=str.substr(pos+1,str.size()-pos);
    for(int k=s2.size();k>=0;k--){
        int j=k,len=0;
        for(int i=0;i<s1.size()&&j<s2.size();i++,j++)
            if(s1[i]==s2[j])
                len++;
        sum=max(len,sum);
    }
    for(int k=1;k<s1.size();k++){
        int i=k,len=0;
        for(int j=0;i<s1.size()&&j<s2.size();i++,j++)
            if(s1[i]==s2[j])
                len++;
        sum=max(len,sum);
    }
    cout<<sum;
}

发表于 2019-09-19 17:21:26 回复(0)
#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000];
int maxx(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int main()
{
    char aa[1000];
    char bb[1000];
    int len1,len2,j,i,max;
    max=0;
    scanf("%[^,]%s",aa,bb);
        len1=strlen(aa);
        len2=strlen(bb)-1;
        //cout<<len1<<endl;
        //cout<<len2<<endl;
        for(i=0;i<=len1;i++) dp[i][0]=0;
        for(j=0;j<=len2;j++) dp[0][j]=0;
        for(i=1;i<=len1;i++)
        {
            for(j=2;j<=len2+1;j++)
            {
                if(aa[i-1]==bb[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    max=maxx(max,dp[i][j]);
                }
                else dp[i][j]=0;
                
                /*else
                {
                    dp[i][j]=maxx(dp[i-1][j],dp[i][j-1]);
                } */
                //printf("%3d",dp[i][j]);
            }
            //printf("\n");
        }
       
        printf("%d\n",max);

}

发表于 2019-08-03 15:54:37 回复(0)
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int longeststring(string a, string b)
{
	int max = -1;
	vector<vector<int>> result(a.size() + 1, vector<int>(b.size() + 1, 0));//注意初始化
	for (int i = 1; i < a.size() + 1; ++i)//计算结果矩阵
	{
		for (int j = 1; j < b.size() + 1; ++j)
		{
			if (a[i - 1] == b[j - 1])
				result[i][j] = result[i - 1][j - 1] + 1;
			else//当不相同时,上边和左边的权值谁大就取谁
				result[i][j] = 0;
			if (max < result[i][j])
			{
		     	max = result[i][j];
				start = i;
			}
		}
	}
	return max;
}
int main()
{
	string str1, str2, zq;
	cin >> zq;
	for (int i = 0; i<zq.size(); ++i)
	{
		if (zq[i] == ',')
		{
			str1 = zq.substr(0, i);
			str2 = zq.substr(i + 1);
			break;
		}
	}//截取出两个字符串
	int length = longeststring(str1, str2, start);
	cout << length;
	return 0;
}

编辑于 2019-08-14 19:07:42 回复(2)
# 伪DP算法
s1,s2 = input().split(',')
if len(s1) < len(s2):       # 保证长串是 s1
    s1,s2 = s2,s1
dp = 0                      # 最大公共子串的长度
for i in range(len(s1)):
    if s1[i-dp:i+1] in s2:
        dp += 1
print(dp)

发表于 2019-08-21 22:53:07 回复(0)
package main

import (
    "fmt"
    "strings"
)

func main() {
    var s string
    fmt.Scan(&s)
    ss:=strings.Split(s,",")
    m,n:=len(ss[0]),len(ss[1])
    mat:=make([][]int,m+1)
    for i,_:=range mat{
        mat[i]=make([]int,n+1)
    }
    max:=0
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if ss[0][i]==ss[1][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)
}

发表于 2023-03-19 08:04:40 回复(0)
动态规划+滚动数组
#include <iostream>
using namespace std;
#include<vector>

int main() 
{
    string str1,str2;
    cin>>str1;
    int pos = str1.find(',');
    str2 = str1.substr(pos+1);
    str1 = str1.substr(0, pos);
    int max = 0;
    vector<int> dp(str1.size()+1, 0);
    for(int i = 1; i <= str1.size(); i++)
    {
        for(int j = str2.size(); j >= 1; j--)
        {
            if(str1[i-1] == str2[j-1])
            dp[j] = dp[j-1]+1;
            else
            dp[j] = 0;
            if(dp[j] > max)
            max = dp[j];
        }
    }
    cout<<max<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2023-01-14 00:54:55 回复(0)
a,m = input().split(',')
maxlen = 0
if len(a) > len(m):
    a, m = m, a
for i in range(len(a)):
    for j in range(len(a)):
        if a[i:j+1] in m:
            if (j+1-i) > maxlen:
                maxlen = j+1-i
print(maxlen)

发表于 2021-01-27 11:01:18 回复(0)
import java.util.*;
public class Main {
        public static void main(String [] args){
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){
                String[] str=sc.next().split(",");
                int max=0;
                for(int i=0;i<str[0].length();i++){
                    for(int j=i+1;j<=str[0].length();j++){
                        if(str[1].contains(str[0].substring(i,j))){
                            max=Math.max(max,str[0].substring(i,j).length());
                        }
                    }
                }
                System.out.println(max);
            }
        }
}


发表于 2020-08-05 20:09:20 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(",");
        int[][] dp = new int[strs[0].length()][strs[1].length()];
        int res=0;
        for(int i=0;i<strs[0].length();i++){
            for(int j=0;j<strs[1].length();j++){
                if(strs[0].charAt(i)==strs[1].charAt(j)){
                    if(i-1<0||j-1<0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                }else{
                    dp[i][j]=0;
                }
                if(dp[i][j]>res)res=dp[i][j];
            }
        }
        System.out.println(res);
    }
}

发表于 2020-06-30 11:14:36 回复(0)
dp经典题目
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 18:29
 * @Description: 最大公共子串
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] ss = sc.nextLine().split(",");
        int[][] dp = new int[ss[0].length()+1][ss[1].length()+1];
        int ans = 0;
        for (int i = 1; i <= ss[0].length(); i++)
            for (int j = 1; j <= ss[1].length(); j++){
                if (ss[0].charAt(i-1) == ss[1].charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        System.out.println(ans);
    }
}


发表于 2020-05-10 18:53:22 回复(0)
a, b = input().split(",")
dp=[[0 for _ in range(len(b) + 1)] for __ in range(len(a) + 1)]
res = 0
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            res = max(res, dp[i][j])
print(res)

发表于 2020-04-07 15:26:42 回复(0)
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String[] str = s.split(",");	//将原字符串进行分割
		System.out.println(getPubLength(str));
	}
	
	
	//获取字符串A与字符串B的最大子串
	public static int getPubLength(String[] str) {
		int max = 0;
		if(str.length > 2) return 0;
		for(int j = 0; j < str[0].length(); j++) {
			for(int i = str[0].length(); i > j; i--) {
				if(str[1].indexOf(str[0].substring(j, i)) != -1) {
					int temp = str[0].substring(j, i).length();
					if(max < temp) max = temp;
				}
			}
		}
		return max;
	}
}

发表于 2019-11-05 19:46:21 回复(0)
s1, s2 = input().split(',')
L1 = len(s1)
L2 = len(s2)
ans = 0
dp = [[0] * (L2 + 1) for _ in range(L1 + 1)]
for i in range(L1):
    for j in range(L2):
        if(s1[i] == s2[j]):
            dp[i+1][j+1] = dp[i][j] + 1
            ans = max(ans, dp[i+1][j+1])
print(ans)
发表于 2019-09-20 19:49:51 回复(0)
滚动数组
#include<iostream>
#include<cstring>
using namespace std;

int dp[2][105];

int main(){
    string s,s1,s2;
    while(cin>>s){
        memset(dp,0,sizeof(dp));
        int i;
        for(i=0;i<s.size();i++){
            if(s[i]==',') break;
        }
        s1=s.substr(0,i),s2=s.substr(i+1);
        int ans=0;
        for(int i=1;i<=s1.size();i++){
            for(int j=1;j<=s2.size();j++){
                if(s1[i-1]==s2[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1;
                else dp[i%2][j]=0;
                ans=max(ans,dp[i%2][j]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
发表于 2019-09-06 14:21:14 回复(0)
动规
a, b = input().split(",")
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
maximum = 0
for i in range(m + 1):
    for j in range(n + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            maximum = max(maximum, dp[i][j])
print(maximum)



发表于 2019-09-03 04:50:24 回复(0)
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    string str,str1,str2;
	int len1,len2;
    cin>>str;
    for(int i=0;i<str.size();i++){
        if(str[i]==','){
			len1=i;
			len2=str.size()-len1-1;
            str1=str.substr(0,i);
            str2=str.substr(i+1,str.size());
            break;
        }
    }
	int m=0;
	int dp[101][101];
	for(int i=0;i<101;i++){
		dp[0][i]=0;
		dp[i][0]=0;
	}
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
			if(str1[i-1]==str2[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=0;
			}
			m=max(m,dp[i][j]);
		}
	}
	cout<<m;
}

编辑于 2019-08-28 13:57:36 回复(0)