字符串中连续出现次数最多的字串

来源:转载

对于字符串abcbcbcabc,连续出现次数最多的字串是bc,注意必须是连续出现。这个题目可以通过逐个字串的扫描来字串出现的次数。

                c      9

              bc      8

            abc      7

           cabc      6

         bcabc      5 

        cbcabc      4

      bcbcabc      3

    cbcbcabc       2

  bcbcbcabc       1

abcbcbcabc       0

#include <iostream>
#include <vector>
#include <string>
using namespace std;


pair<int,string>fun(string &str)
{
vector<string> substrs;
int count = 0;
int maxcount = 0;
string substr;
int len = str.length();
for(int i = 0; i < len; i++)
{
substrs.push_back(str.substr(i,len-i));//将上图的每一行按字符串存入string容器substrs中
}

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[i].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;
}


分享给朋友:
您可能感兴趣的文章:
随机阅读: