【面试题】找出字符串中连续出现次数最多的子串

微软的一道面试题：

如：abcbcbcabc,这个连续出现次数最多的字串是bc

一，考虑边界问题。
二，实现优化笛卡尔积组合，
总体我是这样想的：就是纵向切出字符串的连续组合集合，在横向一对一跳跃比较集合元素。
例如：abcbcabc<wbr><br> 一，纵向切：<br> 得到所有字符串组合，注意：这里要求的是最多连续子字符串，其实就是优化笛卡尔积的原则，也是边界。<br><wbr><span></span>字符串共8位，以子串的长度为1，从字符串第一位开始切，且称为切：<br> 1----从a开始切：(字符串为abcbcabc )<br> 第一次切出a子字符串，得到： a和bcbcabc，<br> 第二次切出ab子字符串，得到： ab和cbcabc，<br> 第三次切出abc子字符串，得到： abc和bcabc，<br> 第四次切出abcb子字符串，得到： abcb和cabc，<br> 第五次切出abcbc子字符串，得到： abcbc和abc，<br> 第六次切出abcbca子字符串，得到： abcbca和bc，<br> 第七次切出abcbcab子字符串，得到： abcbcab和c，<br> 第八次切出abcbcabc子字符串，得到： abcbcabc，<br> 得到a1集合数组（且为数组吧）<br> 元素为：a, ab, abc, ......<br><br> 2---再从b开始切：：(字符串为abcbcabc )<br> 第一次切出b子字符串，得到： b和cbcabc，<br> 第二次切出bc子字符串，得到： bc和bcabc，<br> 第三次切出bcb子字符串，得到： bcb和cabc，<br> 第四次切出bcbc子字符串，得到： bcbc和abc，<br> 第五次切出bcbca子字符串，得到： bcbca和bc，<br> 第六次切出bcbcab子字符串，得到： bcbcab和c，<br> 第七次切出bcbcabc子字符串，得到： bcbcabc<br> 得到b2集合数组（且为数组吧）<br> 元素为：b, bc, bcb ,......<br><br> 3---再从c开始切： (字符串为abcbcabc )<br> 第一次切出c子字符串，得到： c和bcabc，<br> 第二次切出cb子字符串，得到： cb和cabc，<br> 第三次切出cbc子字符串，得到： cbc和abc，<br> 第四次切出cbca子字符串，得到： cbca和bc，<br> 第五次切出cbcab子字符串，得到： cbcab和c，<br> 第六次切出cbcabc子字符串，得到： cbcabc<br> 得到b3集合数组（且为数组吧）<br> 元素为：c, cb, cbc ,......<br><br> 4----再从b开始切： (字符串为abcbcabc )<br> 第一次切出b子字符串，得到： b和cabc，<br> 第二次切出bc子字符串，得到： bc和abc，<wbr><br> 第三次切出bca子字符串，得到： bca和bc，<br> 第四次切出bcab子字符串，得到： bcab和c，<br> 第五次切出bcabc子字符串，得到： bcabc<br> 得到b4集合数组（且为数组吧）<br> 元素为：b, bc, bca ,......<br><br> 5----再从c开始切： (字符串为abcbcabc )<br> 第一次切出c子字符串，得到： c和abc，<br> 第二次切出ca子字符串，得到： ca和bc，<wbr><br> 第三次切出cab子字符串，得到： cab和c，<br> 第四次切出cabc子字符串，得到： cabc<br> 得到c5集合数组（且为数组吧）<br> 元素为：c, ca, cab ,......<br><br> 6----再从a开始切： (字符串为abcbcabc )<br> 第一次切出a子字符串，得到： a和bc，<br> 第二次切出ab子字符串，得到： ab和c，<wbr><br> 第三次切出abc子字符串，得到： abc，<br> 得到a6集合数组（且为数组吧）<br> 元素为：a, ab, abc<wbr><br><br> 7----再从b开始切： (字符串为abcbcabc )<br> 第一次切出b子字符串，得到： b和c，<br> 第二次切出bc子字符串，得到： bc,<wbr><br> 得到b7集合数组（且为数组吧）<br> 元素为：b, bc<br><br> 8----再从c开始切： (字符串为abcbcabc )<br> 第一次切出c子字符串，得到： c<br><br> 得到c8集合数组（且为数组吧）<br> 元素为：c<br><br> 2，横向比：<br> 将a的所有切点按切的顺序保存到称为a1集合数组中（且为数组吧）<br> 将b的所有切点按切的顺序保存到称为b2集合数组中（且为数组吧）<br> 。。。依次类推到完。<br> 得到如下8个集合：（字符串为abcbcabc ）<br> 行数/列数 1 2 3 4 5 6 7 8<br><wbr><span></span>1 a1: a, ab, abc, abcb, abcbc, abcbca , abcbcab, abcbcabc;<br><wbr><span></span>2 b2: b, bc, bcb , bcbc, bcbca, bcbcab, bcbcabc;<br><wbr><span></span>3 c3: c, cb, cbc , cbca, cbcab, cbcabc ;<br><wbr><span></span>4 b4: b, bc, bca , bcab, bcabc;<br><wbr><span></span>5 c5: c, ca, cab , cabc;<br><wbr><span></span>6 a6: a, ab, abc ;<br><wbr><span></span>7 b7: b, bc;<br><wbr><span></span>8 c8: c;<br> 将a1集合，b2集合。。。等全部集合横向比较:<br> 即将列1比较,列2比较跳跃1行比较，列3跳跃2行比较，列3跳跃3行比较。。。。到完；因为要求的是最多连续子字符串，所以要跳跃！<br> 得到相同字符串记数最大值，即求出出现次数最多的子串。<br> 比较方式：<br> 正于前面所说，要求的是最多连续子字符串。其实就是优化笛卡尔积的原则，也是边界。所以我们要做的是将所有集合一对一比较，不是多对多或其他（更简单的理由：位数不同，无需比较）。<br> 多位子字符串一对一比较时候，例如 ab属于a集合和b集合的bc比较，显然没有意义。需要跳跃比较（且这样说吧，呵呵）。跳跃是有规律的。很显然就不说了。<br> 之所以纵切，是为了解决横比较带来的优化问题</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

#include<iostream>
#include<string>
#include<vector>
using namespace std;
pair<int,string> fun(const string &str)
{
 vector<string> substrs;
 int maxcount=1,count =1;
 string substr;
 int i,len = str.length();
 
 for(i =0;i<len;++i)
  
 {
  
  substrs.push_back(str.substr(i,len-i));// //  把abcbcbcabc，bcbcbcabc，cbcbcabc， bcbcabc，cbcabc，bcabc,cabc,abc,bc,c一次放入容器中  
 }
 for(i =0;i<len;i++)
 {
  for(int j =i+1;j<len;j++)
  {
   count =1;
   if(substrs[i].substr(0,j-i)==substrs[j].substr(0,j-i))//第一次循环先单个字符比较，然后再两个，三个字符比较
   {
    ++count;
    for(int k =j+(j-i);k<len;k +=j-i)
    {
     if(substrs[i].substr(0,j-i)==substrs[k].substr(0,j-i))//如果前面比较成功，则需要后面跳跃处理
      ++count;
     else
      break;
    }
    if(count>maxcount)
    {
     maxcount =count;
     substr =substrs[j].substr(0,j-i);
    }
   }
  }
 }
 return make_pair(maxcount,substr);
}
int main()
{
 string str;
 pair<int, string>rs;
 while(cin>>str)
 {
  rs=fun(str);
  cout<<rs.second<<rs.first<<'\n';
 }
 return 0;
}

求一个字符串中连续出现次数最多的子串，例如：abcbcbcabc， 这个串中连续出出次数最多的子串是bc, 它出现了3次。

以下是我的实现代码，用c语言实现，已经编译通过。

#include "stdio.h"
#include "string.h"

 int count = 0; 
 char sub_str[256]; 
 
 void find_str(char *str)  
 { 
     int str_len = strlen(str); 
     int i, j, k; 
     int tmp_cnt = 0; 
 
     for (i = 0; i < str_len; i++) 
     { 
         for (j = i+1; j < str_len; j++) 
         { 
             int n = j-i;                              //sub string length 
             tmp_cnt = 1; 
             if (strncmp(&str[i], &str[j], n) == 0)   //compare n-lengths strings 
             { 
                 tmp_cnt++;                          //they are equal, so add count 
                 for (k = j+n; k < str_len; k += n)  //consecutive checking 
                 { 
                     if (strncmp(&str[i], &str[k], n) == 0) 
                     { 
                         tmp_cnt++; 
                     } 
                    else 
                         break; 
                 } 
                 if (count < tmp_cnt) 
                 { 
                     count = tmp_cnt; 
                     memcpy(sub_str, &str[i], n); //record the sub string 
                 } 
             } 
         } 
 
     } 
 } 
 
 int main() 
 { 
     char *str = "abcbcbcabc"; 
     find_str(str); 
     printf("%d, %s\n", count, sub_str); 
     return 0; 
 }