查找重复代码[A卷-hw_od]

题目描述

小明负责维护项目下的代码，需要查找出重复代码，用以支撑后续的代码优化，请你帮助小明找出重复的代码。 重复代码查找方法：以字符串形式给定两行代码（字符串长度 1 < length <= 100，由英文字母、数字和空格组成），找出两行代码中的最长公共子串。 注：如果不存在公共子串，返回空字符串

输入描述

输入的参数text1, text2分别表示两行代码

输出描述

输出任一最长公共子串

用例1

输入:

hello123world
hello123abc4

输出: 

hello123

用例2

输入:

private_void_method
public_void_method

输出: 

_void_method

用例3

输入:

hiworld
hiweb

输出: 

hiw

代码如下(C++版): 

#include <bits/stdc++.h>
using namespace std;string solve(const string &s1, const string &s2) {int m = s1.size(), n = s2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));int maxLen = 0, endIdx = 0; //维护最大长度和终止索引for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1[i - 1] == s2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > maxLen) {maxLen = dp[i][j];endIdx = j;}}}}return (maxLen > 0) ? s1.substr(endIdx - maxLen, maxLen) : "";
}int main() {string s1, s2;getline(cin, s1);getline(cin, s2);string res= solve(s1, s2);cout << res << endl;return 0;
}

  记忆化搜素(C++):

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> memo;
int maxLen = 0, endIdx = 0;
int dfs(const string &s1, const string &s2, int i, int j) {if (i < 0 || j < 0) return 0;if (memo[i][j] != -1) return memo[i][j];if (s1[i] == s2[j]) {memo[i][j] = dfs(s1, s2, i - 1, j - 1) + 1;if (memo[i][j] > maxLen) {maxLen = memo[i][j];endIdx = i + 1;}} else {memo[i][j] = 0;}return memo[i][j];
}string solve(const string &s1, const string &s2) {int m = s1.size(), n = s2.size();memo.assign(m, vector<int>(n, -1));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs(s1, s2, i, j);}}return (maxLen > 0) ? s1.substr(endIdx - maxLen, maxLen) : "";
}int main() {string s1, s2;getline(cin, s1);getline(cin, s2);string res= solve(s1, s2);cout << res << endl;return 0;
}

 JAVA版:

import java.util.*;
class solve {public String LongestPublicSubstr(String s1, String s2) {int m = s1.length(), n = s2.length();int[][] dp = new int[m + 1][n + 1];int maxLen = 0, endIdx = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > maxLen) {maxLen = dp[i][j];endIdx = i;}}}}return (maxLen > 0) ? s1.substring(endIdx - maxLen, endIdx) : "";}
}
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s1 = sc.nextLine();String s2 = sc.nextLine();solve res=new solve();System.out.println(res.LongestPublicSubstr(s1, s2));}
}

 记忆化搜素(JAVA):

import java.util.*;public class Main {private static int[][] memo;private static int maxLen = 0, endIdx = 0;public static int dfs(String s1, String s2, int i, int j) {if (i < 0 || j < 0) return 0;if (memo[i][j] != -1) return memo[i][j];if (s1.charAt(i) == s2.charAt(j)) {memo[i][j] = dfs(s1, s2, i - 1, j - 1) + 1;if (memo[i][j] > maxLen) {maxLen = memo[i][j];endIdx = i + 1;}} else {memo[i][j] = 0;}return memo[i][j];}public static String solve(String s1, String s2) {int m = s1.length(), n = s2.length();memo = new int[m][n];for (int[] row : memo) Arrays.fill(row, -1);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs(s1, s2, i, j);}}return (maxLen > 0) ? s1.substring(endIdx - maxLen, endIdx) : "";}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s1 = scanner.nextLine();String s2 = scanner.nextLine();System.out.println(solve(s1, s2));}
}

练习链接:1143. 最长公共子序列 - 力扣（LeetCode）

1.上面提供的是LeetCode的练习题，都属于线性DP的类型

2. 本题思路: 上面提供了记忆化搜索和递推的写法

状态定义：dp[i][j]表示以i,j的结尾的最长子串

考虑边界: dp[0][0]=0, dp[m][n]=答案

状态转移: 如果当前s[i]==s[j] , dp[i][j]=dp[i-1][j-1]+1 否则dp[i][j]=0

维护数据: 维护一个结尾索引i/j

注：如果使用的记忆化的解法,memo数组一定不要初始化成0,建议初始化成-1.

如果题目很难, 建议使用记忆化搜索, 但是常见的背包/线性DP之类的题目, 建议直接使用递推

对代码有不理解地方可以直接发到评论区