前言
经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。
描述
查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。
注:子串的定义:将一个字符串删去前缀和后缀(也可以不删)形成的字符串。请和“子序列”的概念分开!
数据范围:字符串长度1≤𝑙𝑒𝑛𝑔𝑡ℎ≤300 1≤length≤300
进阶:时间复杂度:𝑂(𝑛3) O(n3) ,空间复杂度:𝑂(𝑛) O(n)
输入描述:
输入两个字符串
输出描述:
返回重复出现的字符
示例1
输入:
abcdefghijklmnop
abcsafjklmnopqrstuvw
输出:
jklmnop
实现原理与步骤
1.从1个字符到N字符逐次比较字符的一致性,用到了java原生的contains方法
实现代码(暴力算法)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String word1 = in.nextLine();
String word2 = in.nextLine();
int len1 = word1.length();
int len2 = word2.length();
if (len1 < len2) {
String temp = word1;
word1 = word2;
word2 = temp;
}
int maxLen = 0;
String res = "";
for (int i = 0; i < word2.length(); i++) {
for (int j = 0; j <=i; j++) {
String subStr = word2.substring(j, i+1);
if (word1.contains(subStr) && subStr.length() > maxLen) {
res = subStr;
maxLen = subStr.length();
}
}
}
System.out.println(res);
}
}
实现代码(动态规划)
import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s1 = sc.nextLine();
String s2 = sc.nextLine();
System.out.println(longString(s1, s2));
}
}
// 动态规划
public static String longString(String str1, String str2) {
String temp = "";
// 保证str1是较短字符串
if (str1.length() > str2.length()) {
temp = str1;
str1 = str2;
str2 = temp;
}
int m = str1.length();
int n = str2.length();
// 表示在较短字符串str1以第i个字符结尾,str2中以第j个字符结尾时的公共子串长度。
int[][] dp = new int[m+1][n+1];
// 匹配字符,并记录最大值的str1的结尾下标
int max = 0;
int index = 0;
// 从左向右递推,i为短字符串str1的结尾索引,j为str2的结尾索引
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
// 相等则计数
dp[i][j] = dp[i - 1][j - 1] + 1;
// 不断更新变量
if (dp[i][j] > max) {
max = dp[i][j];
index = i;
}
}
}
}
// 截取最大公共子串
return str1.substring(index - max, index);
}
}