【字符串问题】求一个字符串中连续出现次数最多的子串

2013-09-14 10:47:39

在面试宝典上看到的题目，自己做了一下，用了C++中的string类，比较方便。

思路：

遍历源字符串的每一个字符，以该字符为首的重复子串的长度为1到以该字符为首的后缀字符串（即以该字符串为首，到字符结尾的子串，比如abdcef的第三个后缀字符串即为dcef）的长度的一半；
对所有的子串，判断连续重复出现的次数，如果子串连续重复出现的次数大于当前最大连续重复出现的次数，则更新最大连续重复出现的次数。

注意：

VC6.0 对C++的STL支持不是很好，有的方法不支持，如下面代码中的 srcStr.clear();在VS2008中可以运行无措，但在VC6.0中就会报错如下：

error C2039: 'clear' : is not a member of 'basic_string<char,struct std::char_traits<char>,class std::allocator<char> >'

解决方法如下：

用可以完成相同功能的subStr.erase(0,subStr.length());替代，不会报错。

目前还没发现其他更好的办法，如有发现，还请分享一下哦！

代码如下（测试暂未发现错误，欢迎交流指正）：

 1 #include <iostream>
 2 #include <cassert>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 //对string类型，如何测试输入的有效性
 8 size_t FindSubstrAppearMaxtimes(const string srcStr,string &subStr,size_t &count)
 9 {
10     count = 0;
11     subStr.clear();  //或subStr.erase(0,subStr.length());
12     
13     string tmpStr;
14     size_t tmpCount = 0;
15     string tmpStrToComp;
16     size_t posOfSubStr = 0;
17 
18     size_t srcEnd = srcStr.length();
19     size_t srcCurIndex = 0;
20     size_t subLen = 0;
21     size_t subCurIndex = 0;
22 
23     while (srcCurIndex < srcEnd)
24     {
25         for (subLen = 1;2 * subLen <= srcEnd - srcCurIndex;++subLen)
26         {
27             tmpStr = srcStr.substr(srcCurIndex,subLen);
28             tmpCount = 0;
29             tmpStrToComp.erase(0,tmpStrToComp.length());
30 
31             for (subCurIndex = srcCurIndex;subCurIndex < srcEnd;subCurIndex += subLen)
32             {
33                 tmpStrToComp = srcStr.substr(subCurIndex,subLen);
34                 if (tmpStr == tmpStrToComp)   //要加string头文件，才能用==
35                 {
36                     ++tmpCount;
37                 }
38                 else
39                 {
40                     if (tmpCount > count)
41                     {
42                         posOfSubStr = srcCurIndex;
43                         count = tmpCount;
44                         subStr = tmpStr;
45                     }
46                     break;
47                 }
48             }
49         }
50 
51         ++srcCurIndex;
52     }
53 
54     return posOfSubStr;
55 }
56 
57 void TestDriver()
58 {
59     string strArray[] = {"0123456","abcdef","abcbcbcedhellobc","abcbcbcabc","abcccabc"};
60     size_t arrayLength = 5;
61 
62     string srcStr;
63     string subStr;
64     size_t count = 0;
65     size_t posOfSubStr = 0;
66 
67     for (size_t index = 0;index < arrayLength;++index)
68     {
69         srcStr.clear();
70         srcStr = strArray[index];
71         posOfSubStr = FindSubstrAppearMaxtimes(srcStr,subStr,count);
72 
73         cout<<"the source string is : "<<srcStr<<endl;
74         cout<<"the sub string appear most frequently is : "<<subStr<<endl;
75         cout<<"the appearance times is : "<<count<<endl;
76         cout<<endl;
77     }
78 }
79 
80 int main()
81 {
82     TestDriver();
83     return 0;
84 }

测试结果：

the source string is : 0123456
the sub string appear most frequently is : 0
the appearance times is : 1

the source string is : abcdef
the sub string appear most frequently is : a
the appearance times is : 1

the source string is : abcbcbcedhellobc
the sub string appear most frequently is : bc
the appearance times is : 3

the source string is : abcbcbcabc
the sub string appear most frequently is : bc
the appearance times is : 3

the source string is : abcccabc
the sub string appear most frequently is : c
the appearance times is : 3

Press any key to continue