给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。 数据范围：字符串长度：
进阶：时间复杂度：%5C)
，空间复杂度：%5C)
[编程题]公共子串计算
看着讨论区的代码好复杂
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = in.nextLine();
String str2 = in.nextLine();
int maxLength = 0;
for (int i = 0; i < str1.length(); i++) {
for (int j = i; j < str1.length(); j++) {
String substring = str1.substring(i, j + 1);//j + 1需要包含最后一位
if (str2.contains(substring)) {
maxLength = Math.max(maxLength, substring.length());
}
}
}
System.out.println(maxLength);
in.close();
}
}
发表于 2024-09-28 11:57:25
回复(0)
import java.util.*;
//动态规划
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int len1 = str1.length();
int len2 = str2.length();
//状态方程dp[i][j]：字符串1长度为i，字符串2长度为j时最长公共字串长度
int[][] dp = new int[len1 + 1][len2 + 1];
int max = 0;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
//动规表达式,本组相等取前一组相等的长度加1
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(max, dp[i][j]);
}
}
}
System.out.println(max);
}
}
发表于 2024-09-10 15:15:31
回复(0)
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = in.nextLine();
String str2 = in.nextLine();
int length = 0;
for (int i =0; i<str2.length(); i++){
for (int j=0; j<str2.length()-i; j++){
String substring = str2.substring(i, str2.length()-j);
if (str1.contains(substring)){
if (length < substring.length()){
length = substring.length();
}
}
}
}
System.out.println(length);
}
}
发表于 2024-08-02 23:35:45
回复(2)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int res=0;
String s1=in.nextLine();
String s2=in.nextLine();
in.close();
// 暴力解
int res1=comstr(s1,s2);
int res2=comstr(s2,s1);
System.out.println(Math.max(res1,res2));
}
public static int comstr(String s1,String s2){
int res=0;
int len1=s1.length();
int len2=s2.length();
for(int i=0;i<len1;i++){
int temp=0;
for(int j=0;j<len2 && (i+j)<len1;j++){
if(s1.charAt(i+j)==s2.charAt(j)){
temp++;
if(temp>res){
res=temp;
}
}
else{
temp=0;
}
}
}
return res;
}
}
编辑于 2024-04-10 21:48:40
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String str1 = in.nextLine();
String str2 = in.nextLine();
String max = "";
String min = "";
max = (str1.length() > str2.length()) ? str1: str2;
min = (max == str1)? str2: str1;
//System.out.println(max);
//System.out.println(min);
for(int i = min.length(); i>=1; i-- ) {
for(int j = 0,n=i; j<= min.length()-i; j++, n++) {
String sub = min.substring(j, n);
//System.out.println("i: " + i + " j: " +j +" sub: " +sub);
if(max.contains(sub)) {
//System.out.println("contains");
System.out.println(sub.length());
return;
}
}
}
System.out.println(0);
}
}
发表于 2023-10-27 21:30:20
回复(0)
import java.util.Scanner;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
if(str1.length()>str2.length()){
String str =str1;
str1 = str2;
str1 = str;
}
if(str2.contains(str1)){
System.out.println(str1.length());
return;
}
for(int i = 1;i<str1.length();i++){
for(int j = 0;j<=i;j++){
String str;
str = str1.substring(j,str1.length()-(i-j));
if(str2.contains(str)){
System.out.println(str.length());
return;
}
}
}
System.out.println(0);
}
} 19ms,求大佬分析为啥比榜上的慢这么多
发表于 2023-09-21 16:13:18
回复(0)
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line1 = br.readLine();
String line2 = br.readLine();
// 找出短的字符串
String shortStr = line1.length() <= line2.length() ? line1 : line2;
String longStr = line1.length() <= line2.length() ? line2 : line1;
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < shortStr.length(); i++) {
for (int j = i + 1; j <= shortStr.length(); j++) {
String sub = shortStr.substring(i, j);
if (longStr.contains(sub)) {
map.put(sub, sub.length());
}
}
}
// 计算最大长度
if (map.size() > 0) {
Collection<Integer> values = map.values();
int max = Collections.max(values);
System.out.println(max);
} else {
System.out.println(0);
}
}
}
发表于 2023-08-12 12:08:45
回复(0)
import java.util.*;
//动态规划
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1=sc.nextLine();
String str2=sc.nextLine();
int len1=str1.length();
int len2=str2.length();
//状态方程dp[i][j]：字符串1长度为i，字符串2长度为j时最长公共字串长度
int[][] dp=new int[len1+1][len2+1];
int max=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;
max=Math.max(max,dp[i][j]);
}
}
}
System.out.println(max);
}
}
发表于 2023-07-19 18:04:53
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String a=in.next();
String b=in.next();
String c;
int length=0;
for(int i=0;i<a.length();i++)
{for(int d=0;d<a.length()-i;d++)
{ c=a.substring(d,i+d+1);
if(b.contains(c)&&length<c.length())
{
length=c.length();
}
}
}
System.out.print(length);
}
}
发表于 2023-07-13 17:29:13
回复(0)
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
String str1=br.readLine();
String str2=br.readLine();
int len1=str1.length();
int len2=str2.length();
//记录str1的第i字符和str2的第j字符的最长公共子串长度
int[][] dp = new int[len1+1][len2+1];
//maxLCS记录最终的最长公共子串长度
int maxLCS=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
//str1.charAt(i-1)==str2.charAt(j-1)时，最长公共子串长度dp[i][j]等于没有str1的第i
//字符和str2的第j字符参与比较时的最长公共子串长度+1
if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>maxLCS) maxLCS=dp[i][j];
}
}
System.out.println(maxLCS);
}
}
发表于 2023-07-05 18:33:46
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str1 = in.nextLine();
String str2 = in.nextLine();
System.out.println(funHJ75(str1, str2));
}
}
public static int funHJ75(String str1, String str2) {
int result = 0;
String max = str1.length() >= str2.length() ? str1 : str2;
String min = str1.length() >= str2.length() ? str2 : str1;
//i表示substring的跨度，j表示从哪一位开始切片，暴力遍历破解
for (int i = 1; i <= min.length(); i++) {
for (int j = 0; i + j <= min.length(); j++) {
String temp = min.substring(j, j + i);
if (max.contains(temp)) {
result = temp.length();
break;
}
}
}
return result;
}
}
发表于 2023-06-17 15:29:51
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1=in.nextLine();
String str2=in.nextLine();
int maxLength=0;
//表示str1的i位置和str2的j位置时候，最长公共子串的长度为dp[i+1][j+1];
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++){
//如果字符相等的时候
if(str1.charAt(i)==str2.charAt(j)){
//维护dp数组，使其最长长度为i-1,j-1的位置长度+1
dp[i+1][j+1]=dp[i][j]+1;
//维护最大长度
if(dp[i+1][j+1]>maxLength){
maxLength=dp[i+1][j+1];
}
//不等说明当前位置最大长度为0
}else{
dp[i+1][j+1]=0;
}
}
}
System.out.print(maxLength);
}
}
发表于 2023-06-06 08:40:22
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String str1 = in.nextLine();
String str2 = in.nextLine();
if(str1.length()>str2.length()){
String temp = str1;
str1 =str2;
str2 = temp;
}
String[] str1Arr = str1.split("");
String[] str2Arr = str2.split("");
int maxLen = 0;
for(int i = 0;i < str1Arr.length; i++){
int temp = 0;
for(int j = 0,k = i;j<str2Arr.length&&k<str1Arr.length;j++){
String m = str1Arr[k];
String n = str2Arr[j];
if(m.equals(n)){
temp++;
k++;
}else{
if(temp>maxLen) maxLen=temp;
temp=0;
k=i;
}
}
if(temp>maxLen) maxLen=temp;
}
System.out.println(maxLen);
}
}
} cbbcbdcdacacdabbdaabcdcacabdcbcbdcddcbcdcbbbddbbcccdccbbacbaccabcbadbddaaaaadcc
abdcdbbcbcddbaddccdabbddabbdcbdaaacbddcabbbaabbcbddcaddaaccbccbbaaccaccacbcbbcadbccaa
自己的代码结果是5，答案是6，其他用例都过了（12/13）这咋看
发表于 2023-05-12 22:01:55
回复(0)
import java.util.Scanner;
/*
* 公共子串计算
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int row = str1.length() + 1;
int col = str2.length() + 1;
int max = 0;
int [][]dp = new int [row][col];
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Math.max(max, dp[i][j]);
}
}
System.out.println(max);
}
}
发表于 2023-03-28 09:54:00
回复(0)
主要是需要注意边界
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = in.next();
String str2 = in.next();
char[] schar1 = str1.toCharArray();
char[] schar2 = str2.toCharArray();
int max = 0;
int[][] dp = new int[schar1.length][schar2.length];
for (int i = 0; i < schar1.length; i++) {
for (int j = 0; j < schar2.length; j++) {
if (schar1[i] == schar2[j]) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
max = Math.max(max, dp[i][j]);
}
}
System.out.println(max);
}
}
发表于 2023-03-19 17:15:45
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String a = in.nextLine();
String b = in.nextLine();
int len1 = a.length();
int len2 = b.length();
int max = 0;
int samelen=0;
String tmp;
for (int i = 0; i < len1; i++)
for (int j = i + 1; j <=len1; j++) {
tmp = a.substring(i, j);
samelen = len2 - b.replaceFirst(tmp, "").length();
max = samelen > max ? samelen : max;
// System.out.println(tmp+","+max+","+b.replace(tmp, ""));
}
System.out.println(max);
}
}
}
发表于 2023-03-12 17:46:52
回复(0)
二维数组的动态规划
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 获取输入的字符串
String str1 = in.nextLine();
String str2 = in.nextLine();
// 将字符串转换为字符数组
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
// 定义一个二维数组，用来存贮第i,j位置的最大公共字串的长度
int[][] dp = new int[str1.length()+1][str2.length()+1];
// 定义一个变量，用来得到最大功能字串的长度
int maxLength = 0;
// 通过循环查找最大功能字串
for (int i = 1; i <= char1.length; i++) {
for (int j = 1; j <= char2.length; j++) {
if (char1[i-1] == char2[j-1]) {
// i，j位置的最大公共字串即为i-1,j-1位置的最大公共字串加上本身就OK
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 不等，ij位置最大公共字串即为0；
dp[i][j] = 0;
}
maxLength = Math.max(maxLength, dp[i][j]);
}
}
// 输出结果
System.out.println(maxLength);
}
}
发表于 2023-02-15 11:37:13
回复(0)
一段时间不写 有点懵逼了
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
private Integer[][] memo;
private int res = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) { // 注意 while 处理多个 case
String a = in.nextLine();
String b = in.nextLine();
Main m = new Main();
System.out.println(m.lcs(a, b));
}
}
public int lcs(String a, String b) {
int m = a.length();
int n = b.length();
int max = 0;
// dp[i][j] : a[i-1]结尾和b[j-1]结尾 的最长公共连续子串
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(max, dp[i][j]);
}else {
dp[i][j] = 0;
}
}
}
return max;
}
}
发表于 2022-11-02 17:38:36
回复(0)
问题信息
难度：
68条回答
2074收藏
47118浏览
通过挑战的用户
查看代码-
2023-03-04 10:16:08 -
2023-02-27 16:21:07
-
2023-02-20 20:58:38 -
2022-11-09 12:07:56
-
2022-11-08 21:03:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
