字符环

【描述】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

有两个由字符构成的环。请写一个程序，计算这两个字符环上最长连续公共字符串的长度。例如，字符串“ABCEFAGADEGKABUVKLM”的首尾连在一起，构成一个环；字符串“MADJKLUVKL”的首尾连在一起，构成一个另一个环；“UVKLMA”是这两个环的一个连续公共字符串。7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

一行，包含两个字符串，分别对应一个字符环。这两个字符串之间用单个空格分开。字符串长度不超过255，且不包含空格等空白符。7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输出】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出一个整数，表示这两个字符环上最长公共字符串的长度。7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【样例输入】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

ABCEFAGADEGKABUVKLM MADJKLUVKL

【样例输出】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

6

【参考程序】7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

C++版本7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 7ut100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. #include <iostream> 
2. #include <string> 
3. #include <algorithm> 
4.  
5. using namespace std; 
6.  
7. int main() 
8. { 
9.     int x, y, len, len1, len2, limit, ans = 0; 
10.     string s1, s2; 
11.     cin >> s1 >> s2; 
12.     len1 = s1.size(); 
13.     len2 = s2.size(); 
14.     limit = min(len1, len2);//最短字符串的长度 
15.     s1 += s1; // 造环 
16.     s2 += s2; // 造环 
17.     for (int i = 0; i < len1; i++) 
18.     { 
19.         for (int j = 0; j < len2; j++) 
20.         { 
21.             len = 0; 
22.             x = i; 
23.             y = j; 
24.             while (s1[x++] == s2[y++] && len < limit)//不能超过段长 
25.             { 
26.                 len++; 
27.             } 
28.             if (len > ans) 
29.             { 
30.                 ans = len; 
31.             } 
32.         } 
33.     } 
34.     cout << ans << endl; 
35.     return 0; 
36. }