字符环 时间限制：C/C++ 1000MS 内存限制：C/C++ 256MB

Question

字符环

描述

有两个由字符构成的环。请写一个程序，计算这两个字符环上最长连续公共字符串的长度。例如，字符串“ ABCEFAGADEGKABUVKLM ”的首尾连在一起，构成一个环；字符串“ MADJKLUVKL ”的首尾连在一起，构成一个另一个环；“ UVKLMA ”是这两个环的一个连续公共字符串。

输入描述

一行，包含两个字符串，分别对应一个字符环。这两个字符串之间用单个空格分开。字符串长度不超过255 ，且不包含空格等空白符。

输出描述

输出一个整数，表示这两个字符环上最长公共字符串的长度。

样例输入 1

ABCEFAGADEGKABUVKLM MADJZXZKLUVKL
样例输出 1

6

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

## 问题描述 我们需要编写一个程序，以计算两个字符环上最长连续公共字符串的长度。字符环是指一个字符串可以首尾相连，形成环状结构。输入由两个字符串组成，需计算并输出它们的最长公共子串的长度。

输入描述

• 输入为一行，包含两个字符串，使用单个空格分隔。
• 字符串长度不超过255且不包含空格等其他空白符。

输出描述

• 输出一个整数，表示两个字符环上最长公共字符串的长度。

解题思路

1. 连接字符串: 将字符串A和字符串B分别重复一遍（即连接自己），以便模拟环的特性。

   • 例如，字符串A = "ABCEFAGADEGKABUVKLM"可以变为"ABCEFAGADEGKABUVKLMA"。

2. 使用动态规划或滑动窗口: 针对每个可能的起始位置，寻找另一个字符串中的最长公共子串。

3. 求解并输出结果: 找到最长公共子串的长度并输出。

示例

输入示例

ABCEFAGADEGKABUVKLM MADJZXZKLUVKL

输出示例

6

这表明在这两个环中，最长的连续公共字符是"UVKLMA"，其长度为6。

Python代码实现

下面是采用动态规划的解法来解决本问题的Python代码实现：

def longest_common_substring(s1, s2):
    n = len(s1)
    m = len(s2)
    # 创建一个(n+1) x (m+1)的二维数组
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    longest_len = 0
    # 循环计算最长公共子串的长度
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                longest_len = max(longest_len, dp[i][j])
            else:
                dp[i][j] = 0
    return longest_len
def find_longest_circle_common_length(s1, s2):
    # 将两个字符串各自拼接成环
    doubled_s1 = s1 + s1
    doubled_s2 = s2 + s2
    max_length = 0
    # 计算s1与s2的最长公共子串长度
    for i in range(len(s1)):
        current_length = longest_common_substring(doubled_s1[i:i+len(s1)], doubled_s2)
        max_length = max(max_length, current_length)
    return max_length
# 输入部分
input_string = input().strip()
s1, s2 = input_string.split()
# 输出最长公共子串长度
result = find_longest_circle_common_length(s1, s2)
print(result)

代码说明

1. longest_common_substring函数使用动态规划求解两个字符串的最长公共子串长度。
2. find_longest_circle_common_length函数处理输入的两个字符串，生成相应的环字符串，并调用longest_common_substring进行计算。
3. 主程序部分接收输入并输出结果。 使用这个代码后，能够有效计算并输出两个字符环上最长公共子串的长度。