2013-09-14 10:47:39

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

思路：

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

 

注意：

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 
     
       2 #include 
      
        3 #include 
       
         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                 else39                 {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 : "<
        
         <
        
       
      
     

测试结果：

the source string is : 0123456the sub string appear most frequently is : 0the appearance times is : 1the source string is : abcdefthe sub string appear most frequently is : athe appearance times is : 1the source string is : abcbcbcedhellobcthe sub string appear most frequently is : bcthe appearance times is : 3the source string is : abcbcbcabcthe sub string appear most frequently is : bcthe appearance times is : 3the source string is : abcccabcthe sub string appear most frequently is : cthe appearance times is : 3Press any key to continue