跳至主要內容

【DP】2024E-寻找重复代码

【DP】2024E-寻找重复代码

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3440

题目

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

注意子串是连续的。

输入

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

输出

输出任一最长公共子串。

示例一

输入

hello123world
hello123abc4

输出

hello123

示例二

输入

private_void_method
public_void_method

输出

_void_method

示例三

输入

hiworld
hiweb

输出

hiw

解题思路

注意：本题和LC718. 最长重复子数组几乎完全一致。唯一区别在于，本题要计算的不是最长公共子串的长度，而是要输出最长公共子串本身。

这是一个典型的dp问题。我们考虑动态规划三部曲：

  1. dp数组的含义是什么？
  • dp数组是一个大小为(N+1)*(M+1)的二维矩阵，dp[i][j]表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的连续子串的长度。
  1. 动态转移方程是什么？
  • 如果发现 text1 的当前元素，即位置为 i-1 的元素，与 text2 的当前元素即位置为 j-1 的元素**相同。**此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1。
if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
  1. dp数组如何初始化？
  • dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度，此时公共的、长度最长的子串的长度为 0。
  • text1 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0。
dp = [[0] * (n + 1) for _ in range(m + 1)]

dp[0][0] = 0

for i in range(1, m+1):
    dp[i][0] = 0

for j in range(1, n+1):
    dp[0][j] = 0

考虑完上述问题后，代码其实呼之欲出了。

代码

Python

# 题目：2024E-寻找重复代码
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：动态规划（LCS问题）
# 代码看不懂的地方，请直接在群上提问


text1 = input()
text2 = input()

# 获取 text1 的长度
m = len(text1)

# 获取 text2 的长度
n = len(text2)

# 设置数组 dp，用来存储 text1 和 text2 公共的、长度最长的子串的长度
# dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度
# dp[2][3] 表示 text1 前 2 个元素和 text2 前 3 个元素的公共的、长度最长的子串的长度
# dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度
# 前 i 个元素的区间为 [0, i-1]
# dp[m][n] 表示 text1 前 m 个元素和 text2 前 n 个元素的公共的、长度最长的子串的长度
# 前 m 个元素的表示区间为 [0, m]，前 n 个元素的表示区间为 [0, n]
# 因此，dp 数组的长度为 m + 1 和 n + 1
dp = [[0] * (n + 1) for _ in range(m + 1)]

# maxLength 表示 dp 数组中的最大值
maxLength = 0

# 初始化答案变量为空串
ans = ""

# 1. 初始化dp数组
# dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度
# text1 text2 也没有元素
# 因此，公共的、长度最长的子串的长度为 0
dp[0][0] = 0

# text1 没有元素 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0
for i in range(1, m+1):
    dp[i][0] = 0

for j in range(1, n+1):
    dp[0][j] = 0

# i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个元素
for i in range(1, m+1):
    # j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个元素
    for j in range(1, n+1):
        
        # 2. 动态转移方程
        # 如果发现 text1 的当前元素，即位置为 i - 1 的元素
        # 与 text2 的当前元素，即位置为 j - 1 的元素【相同】
        # 此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1
        if  text1[i - 1] == text2[j - 1]:

            # dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度
            # dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度
            dp[i][j] = dp[i - 1][j - 1] + 1

            # 更新最长的子串的长度
            if maxLength < dp[i][j]:
                maxLength = dp[i][j]
                # 最长子串长度为maxLength，对于text1而言，
                # 当前结束位置为i，当前开始位置为i-maxLength
                # 这里换成text2[j-maxLength: j]也是一样的
                ans = text1[i-maxLength: i]

# 返回结果
print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String text1 = scanner.nextLine();
        String text2 = scanner.nextLine();
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;
        String ans = "";

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (maxLength < dp[i][j]) {
                        maxLength = dp[i][j];
                        ans = text1.substring(i - maxLength, i);
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string text1, text2;
    getline(cin, text1);
    getline(cin, text2);

    // 获取 text1 的长度
    int m = text1.length();

    // 获取 text2 的长度
    int n = text2.length();

    // 设置数组 dp，用来存储 text1 和 text2 公共的、长度最长的子串的长度
    // dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度
    // dp[2][3] 表示 text1 前 2 个元素和 text2 前 3 个元素的公共的、长度最长的子串的长度
    // dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度
    // 前 i 个元素的区间为 [0, i-1]
    // dp[m][n] 表示 text1 前 m 个元素和 text2 前 n 个元素的公共的、长度最长的子串的长度
    // 前 m 个元素的表示区间为 [0, m]，前 n 个元素的表示区间为 [0, n]
    // 因此，dp 数组的长度为 m + 1 和 n + 1
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // maxLength 表示 dp 数组中的最大值
    int maxLength = 0;

    // 初始化答案变量为空串
    string ans = "";

    // 1. 初始化dp数组
    // dp[0][0] 表示 text1 前 0 个元素和 text2 前 0 个元素的公共的、长度最长的子串的长度
    // text1 text2 也没有元素
    // 因此，公共的、长度最长的子串的长度为 0
    dp[0][0] = 0;

    // text1 没有元素 或者 text2 没有字符时，公共的、长度最长的子串的长度都为 0
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = 0;
    }

    for (int j = 1; j <= n; ++j) {
        dp[0][j] = 0;
    }

    // i 从 1 开始，直到 m 位置，遍历 text1 的前 i 个元素
    for (int i = 1; i <= m; ++i) {
        // j 从 1 开始，直到 n 位置，遍历 text2 的前 j 个元素
        for (int j = 1; j <= n; ++j) {
            // 2. 动态转移方程
            // 如果发现 text1 的当前元素，即位置为 i - 1 的元素
            // 与 text2 的当前元素，即位置为 j - 1 的元素【相同】
            // 此时，找到了一个公共元素，公共的、长度最长的子串的长度加 1
            if (text1[i - 1] == text2[j - 1]) {
                // dp[i][j] 表示 text1 前 i 个元素和 text2 前 j 个元素的公共的、长度最长的子串的长度
                // dp[i - 1][j - 1] 表示 text1 前 i - 1 个元素和 text2 前 j - 1 个元素的公共的、长度最长的子串的长度
                dp[i][j] = dp[i - 1][j - 1] + 1;

                // 更新最长的子串的长度
                if (maxLength < dp[i][j]) {
                    maxLength = dp[i][j];
                    // 最长子串长度为maxLength，对于text1而言，
                    // 当前结束位置为i，当前开始位置为i-maxLength
                    // 这里换成text2[j-maxLength: j]也是一样的
                    ans = text1.substr(i - maxLength, maxLength);
                }
            }
        }
    }

    // 返回结果
    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* findLongestCommonSubstring(char* text1, char* text2) {
    int m = strlen(text1);
    int n = strlen(text2);

    // 动态分配 dp 数组
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)calloc(n + 1, sizeof(int));
    }

    int maxLength = 0; // 记录最长公共子串的长度
    int endIndex = 0;  // 记录最长子串在 text1 中的结束索引

    // 遍历 text1 和 text2 的所有字符
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;

                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    endIndex = i;
                }
            }
        }
    }

    // 提取最长公共子串
    char* ans = (char*)malloc((maxLength + 1) * sizeof(char));
    strncpy(ans, text1 + endIndex - maxLength, maxLength);
    ans[maxLength] = '\0';

    // 释放动态分配的内存
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);

    return ans;
}

int main() {
    char text1[1001], text2[1001];
    scanf("%s %s", text1, text2);

    char* result = findLongestCommonSubstring(text1, text2);
    printf("%s\n", result);

    free(result); // 释放返回字符串的内存
    return 0;
}

Node JavaScript

function findLongestCommonSubstring(text1, text2) {
    const m = text1.length;
    const n = text2.length;

    // 初始化 dp 数组
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    let maxLength = 0; // 记录最长公共子串的长度
    let endIndex = 0;  // 记录最长子串在 text1 中的结束索引

    // 遍历 text1 和 text2 的所有字符
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;

                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    endIndex = i;
                }
            }
        }
    }

    // 提取最长公共子串
    return text1.slice(endIndex - maxLength, endIndex);
}

// 测试主函数
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (line1) => {
    rl.question('', (line2) => {
        console.log(findLongestCommonSubstring(line1, line2));
        rl.close();
    });
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
)

func findLongestCommonSubstring(text1, text2 string) string {
        m, n := len(text1), len(text2)

        // 初始化 dp 数组
        dp := make([][]int, m+1)
        for i := range dp {
                dp[i] = make([]int, n+1)
        }

        maxLength := 0    // 记录最长公共子串的长度
        endIndex := 0     // 记录最长子串在 text1 中的结束索引

        // 遍历 text1 和 text2 的所有字符
        for i := 1; i <= m; i++ {
                for j := 1; j <= n; j++ {
                        if text1[i-1] == text2[j-1] {
                                dp[i][j] = dp[i-1][j-1] + 1

                                if dp[i][j] > maxLength {
                                        maxLength = dp[i][j]
                                        endIndex = i
                                }
                        }
                }
        }

        // 提取最长公共子串
        return text1[endIndex-maxLength : endIndex]
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        text1, _ := reader.ReadString('\n')
        text2, _ := reader.ReadString('\n')

        // 去掉末尾的换行符
        text1 = text1[:len(text1)-1]
        text2 = text2[:len(text2)-1]

        result := findLongestCommonSubstring(text1, text2)
        fmt.Println(result)
}

时空复杂度

时间复杂度：O(MN)。dp过程需要经历双重循环。

空间复杂度：O(MN)。二维dp数组所占据的空间。

M、N分别为text1、text2的长度。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法