算法设计：最长公共子串

最长公共子串问题是一个经典的字符串处理问题，旨在找出给定两个字符串中的最长公共子串。其中，子串是指从原字符串中连续删除一些字符，而子序列是指从原字符串中删除一些字符，但不必连续。

解决最长公共子串问题的一种常见方法是使用动态规划算法。动态规划主要解决具有重叠子问题和最优子结构性质的问题，通过将问题分解为子问题，并存储子问题的解来避免重复计算，从而提高算法的效率。

动态规划算法实现

#include 
#include 
#include 

using namespace std;

string longestCommonSubstring(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector> dp(m + 1, vector(n + 1, 0));
    int maxLen = 0;
    int endIndex = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i - 1;
                }
            }
        }
    }

    return str1.substr(endIndex - maxLen + 1, maxLen);
}

int main() {
    string str1 = "abcdefg";
    string str2 = "abdefg";
    string result = longestCommonSubstring(str1, str2);
    cout << "最长公共子串为：" << result << endl;

    return 0;
}

算法解释与分析

上述代码中的动态规划算法使用了一个二维数组dp来存储最长公共子串的长度。dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子串的长度。

对于每个str1[i-1]和str2[j-1]，如果相等，则最长公共子串的长度可以通过在str1[i-1]和str2[j-1]前的最长公共子串长度dp[i-1][j-1]基础上加1得到。如果不相等，则最长公共子串的长度为0。

在计算最长公共子串的过程中，同时记录最长公共子串的长度maxLen和索引endIndex。最后通过substr函数从str1中截取最长公共子串并返回。

总结

最长公共子串算法是一种常用的字符串处理算法，通过动态规划的思想，可以高效地找到给定两个字符串中的最长公共子串。该算法的时间复杂度为O(m*n)，其中m和n分别为两个字符串的长度。在实际应用中，最长公共子串问题常常被用于文本相似性匹配、DNA序列分析等领域。