牛客笔试题---求最长重复词长度之和

　　①题目要求：

　　对于两个字符串B和C，我们定义BC为将C接在B的后面形成的新串。一个字符串P是串A的前缀，当且仅当存在B使得A＝PB，当然B可以为空串。若P!=A,则我们称P为A的真前缀。现在定义重复词。串Q是串A的重复词当且仅当Q是A的真前缀，且A是QQ的前缀。而A的最长重复词则是A的重复词中最长的一个，或者空串（当A没有任何重复串时）。如ababab的最长重复词是abab;abc的最长重复词是空串。

　　给定一个串s(由字母组成)，及它的长度n(1≤n≤100000)，请返回s的所有前缀的最长重复词的长度之和(空串长度为0)。

　　测试样例：

　　8,"babababa"

　　返回：24


实现：

 1 #include<string>
 2 class Periods {
 3 public:
 4     long long getLongest(int n, string s) {
 5         // write code here
 6         long long    res = 0;
 7 
 8         //1求所有前缀
 9         for (int i = 0; i <= n; i++)
10         {
11             
12             string subS = s.substr(0, i);        //前缀
13 
14             bool get = false;    //是否获得最长重复词
15 
16             //判断是否是重复词。//要求之一是qq 有前缀A所以长度限制
17             for (int k = i-1; k >= i / 2; k--)
18             {
19                 //真前缀  i-1 保证
20                 string subsubS = subS.substr(0, k);
21                 
22                 //前缀
23                 string supS = subsubS + subsubS;
24                 string tmp = supS.substr(0, subS.length());
25                 if (subS == tmp)
26                 {
27                     get = true;
28                     cout << subS << ":::::" << "	";
29                     cout << subsubS << endl;
30                     res += subsubS.length();
31                 }
32                 else if (get == true)break;
33             }
34         }
35         return res;
36     }
37 };

测试：

 1 void main()
 2 {
 3     Periods per;
 4     string s1 = "babababa";
 5     cout << per.getLongest(8, s1) << endl;
 6 
 7     s1 = "baaaba";
 8     cout << per.getLongest(6, s1) << endl;
 9 
10     s1 = "babababaa";
11     cout << per.getLongest(9, s1) << endl;
12 
13     s1 = "";
14     cout << per.getLongest(0, s1) << endl;
15 
16 }

输出：

　　8
　　24
　　0
　　请按任意键继续. . .