加载中…
个人资料
一叶知秋
一叶知秋
  • 博客等级:
  • 博客积分:0
  • 博客访问:424,864
  • 关注人气:82
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

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

(2013-07-01 21:33:06)
标签:

it

分类: 数据结构与算法

 

基本算法描述:
    给出一个字符串abababa 
    1.穷举出所有的后缀子串
        substrs[0] = abababa;
        substrs[1] = bababa;
        substrs[2] = ababa;
        substrs[3] = baba;
        substrs[4] = aba;
        substrs[5] = ba;
        substrs[6] = a;
    2.然后进行比较
        substrs[0]比substrs[1]多了一个字母,如果说存在连续匹配的字符,那么
        substrs[0]的第1个字母要跟substrs[1]首字母匹配,同理
        substrs[0]的前2个字母要跟substrs[2]的前2个字母匹配(否则不能叫连续匹配)
        substrs[0]的前n个字母要跟substrs[n]的前n个字母匹配.
  上述每次的遍历过程中,如果出现匹配,就依次比较后续的拥有相同长度的子串
        最终记下匹配次数.取最大值作为最长连续匹配子串.     

#include<iostream>
#include<string>
#include<vector>

using namespace std;

pair<int, string> fun (const string &str)
{
    vector<string> substrs;
    int maxcount = 1;
    int count =1;
    string substring ;
    int i,j,k;
    int length = str.length();

    //生成字符串所有的后缀子串
    for(i=0; i<length; i++)
    {
        substrs.push_back(str.substr(i, length-i));
     }

    for(i=0; i<length; ++i)//从substr[0]开始遍历,依次和后续的子串比较,只比较前缀
    {
  
        for(j=i+1; j<length; ++j)//后缀数组中substrs[i]之后的元素依次与substrs[i]比较
        {
            count =1;
            if(substrs[i].substr(0, j-i) == substrs[j].substr(0, j-i))//如果相等,计数加一;
            {
               count++;
               for(k=j+(j-i); k<length; k+=(j-i))//同时依次比较后续相等长度的子串
               {
                  if(substrs[i].substr(0, j-i) == substrs[k].substr(0, j-i))
                     count++;
                  else
                      break;
               }
               if(count >= maxcount)
               {
                   maxcount = count;
                   substring = substrs[i].substr(0, j-i);
               }
           
       }
   }
   return make_pair(maxcount, substring);
}
int main()
{
    string str;
    pair<int,string> rs;
    while(cin>>str)
    {
       rs =fun(str);
       cout<<rs.second<<':'<<rs.first<<'\n';
    }
    return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有