前言

經過前期的數據結構和算法學習，開始以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);}
}

1.QA: