给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。 数据范围：字符串长度：
进阶：时间复杂度：%5C)
，空间复杂度：%5C)
[编程题]公共子串计算
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)
动态规划，使用滚动数组
使用滚动数组，将常规的二维数组dp优化成一维数组
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while(Objects.nonNull(str = br.readLine())) {
String s1 = str, s2 = br.readLine();
int ans = longest(s1,s2);
System.out.println(ans);
}
}
private static int longest(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length(), max = 0;
int dp[] = new int[len2 + 1];
for (int i = 1; i <= len1; ++i) {
int lt = dp[0]; // 可看作二维数组中，dp[i - 1][j - 1];
dp[0] = 0;
for (int j = 1; j <= len2; ++j) {
int temp = dp[j]; // 在更新前，表示的为dp[i - 1][j];
dp[j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? lt + 1 : 0;
lt = temp;
max = Math.max(dp[j], max);
}
}
return max;
}
发表于 2022-09-08 09:45:08
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
String dest = scanner.nextLine();
int[][] elem = new int[str.length() + 1][dest.length() + 1];
elem[0][0] = 0;
//定义数组时 默认为0
int max = 0;
for (int i = 1; i <= str.length(); i++) {
for (int j = 1; j <= dest.length(); j++) {
if (str.charAt(i - 1) == dest.charAt(j - 1)) {
elem[i][j] = elem[i - 1][j - 1] + 1;
}
max=Math.max(elem[i][j],max);
}
}
System.out.println(max);
}
}
发表于 2022-09-05 23:38:55
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
public class Main {
public static void maxLength (String minStr,String maxStr){
int len = minStr.length();
ArrayList <String> arr =new <String> ArrayList();
int maxLen =0;
for(int i=0;i<len;i++){
for(int j=i+1;j<=len;j++){
// arr.add();
String stt = minStr.substring(i,j);
if(maxStr.contains(stt)){
if(maxLen<stt.length())
maxLen = stt.length();
}
}
}
System.out.print(maxLen);
}
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
String str1 = scan.next();
String str2 = scan.next();
int k =0;
if(str1.length()>str2.length()){
maxLength(str2,str1);
}else{
maxLength(str1,str2);
}
}
}
发表于 2022-08-30 10:46:54
回复(0)
问题信息
难度：
65条回答
1872收藏
45409浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
