给定两个字符串,请编写代码,输出最长公共子串(Longest Common Substring),是指两个字符串中的最长的公共子串,要求子串一定是连续。
数据范围:输入的两个字符串长度满足
#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; }
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); } }
#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 */
#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; }
#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; }
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) }
动态规划+滚动数组 #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")
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); } } }
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); } }
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); } }
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)
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; } }
#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; }