最长公共子串的长度 描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度（假设str1和str2的最长公共子串存在且唯一）。

最长公共子串问题可以使用动态规划求解。

定义一个二维数组dp，其中dp[i][j]表示以str1[i]和str2[j]结尾的最长公共子串的长度。如果str1[i]和str2[j]不相等，则dp[i][j]=0；如果相等，则有dp[i][j]=dp[i-1][j-1]+1。

最终的最长公共子串的长度就是dp数组中的最大值。

以下是Python代码实现：

def longest_common_substring(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * n for _ in range(m)]
    max_len = 0
    for i in range(m):
        for j in range(n):
            if str1[i] == str2[j]:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

例如，对于字符串"abcdefg"和"bcdeff"，最长公共子串为"bcdef"，长度为5。

相关问题

用java实现：最长公共子串的长度 描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度（假设str1和str2的最长公共子串存在且唯一）。

以下是用Java实现最长公共子串长度的示例代码：

public class LongestCommonSubstring {
    public static int longestCommonSubstring(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int maxLength = 0;
        int[][] dp = new int[m+1][n+1];
        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;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String str1 = "abcdxyz";
        String str2 = "xyzabcd";
        int maxLength = longestCommonSubstring(str1, str2);
        System.out.println("The length of longest common substring is " + maxLength);
    }
}

以上代码使用动态规划算法来解决该问题。通过定义一个二维数组`dp`，其中`dp[i][j]`表示以`str1`的第`i`个字符和`str2`的第`j`个字符为结尾的最长公共子串的长度。当`str1.charAt(i-1) == str2.charAt(j-1)`时，表示`str1`和`str2`的第`i`和`j`个字符相同，因此可以通过`dp[i-1][j-1]`得到以`str1`的第`i-1`个字符和`str2`的第`j-1`个字符为结尾的最长公共子串长度，并加上当前相同的字符，即可得到以`str1`的第`i`个字符和`str2`的第`j`个字符为结尾的最长公共子串的长度。同时，需要记录每次更新的最大长度，并在遍历完成后返回该长度。

问题1：给定两个字符串str1和str2，输出两个字符串的最长公共子串，保证str1和str2的最长公共子串存在且唯一。 要求： （1）数据输入：字符串元素随机生成。 （2）数据输出：最长公共子串。写出c++代码

要解决这个问题，可以使用动态规划的方法来找到两个字符串的最长公共子串。下面是一个C++代码示例：

#include <iostream>
#include <string>

std::string longestCommonSubstring(const std::string& str1, const std::string& str2) {
    int m = str1.length();
    int n = str2.length();
    int dp[m + 1][n + 1];
    int maxLength = 0;
    int endIndex = -1;

    // 初始化动态规划数组
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = 0;

            // 更新最长公共子串信息
            if (dp[i][j] > maxLength) {
                maxLength = dp[i][j];
                endIndex = i - 1;
            }
        }
    }

    // 从右下角回溯构建最长公共子串
    std::string result;
    while (maxLength > 0) {
        result += str1[endIndex];
        maxLength--;
        endIndex--;
    }
    return result; // 反转结果，因为回溯是从右下角开始的
}

int main() {
    std::string str1 = "hello world";
    std::string str2 = "world is beautiful";
    std::cout << "Longest common substring: " << longestCommonSubstring(str1, str2) << std::endl;
    return 0;
}

这段代码首先创建了一个二维动态规划数组`dp`，用于存储每个位置上的最长公共子串长度。然后通过比较字符找出当前位置的最长公共子串长度，并更新最长子串的信息。最后，从最后一个已知的最长公共子串长度的位置回溯，构造出完整的最长公共子串。