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

这是一个经典的计算机科学问题，通常被称为"环形字符串匹配"或"环状最长公共子序列"（Cyclic Longest Common Subsequence）。你可以通过滑动窗口算法来解决这个问题。以下是Python的一个简单实现：

def longest_common_substring(ring1, ring2):
    # 将两个环转换成线性的字符串，方便处理
    linear_str1 = ring1 + ring1[0]
    linear_str2 = ring2 + ring2[0]

    n1, n2 = len(linear_str1), len(linear_str2)
    dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]

    max_len = 0
    end_index = 0

    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            if linear_str1[i - 1] == linear_str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_index = i
            else:
                dp[i][j] = 0

    return max_len, linear_str1[end_index - max_len:end_index]

ring1 = "ABCEFAGADEGKABUVKLM"
ring2 = "MADJKLUVKL"

length, common_substring = longest_common_substring(ring1, ring2)
print(f"最长连续公共字符串的长度是 {length}，串是 '{common_substring}'")