注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

仰望天空

记得常常仰望天空,记住仰望天空的时候也看看脚下

 
 
 

日志

 
 

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

2011-10-07 00:27:04|  分类: 学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
转自 http://www.cnblogs.com/this-543273659/archive/2011/08/03/2126572.html

vector向量中的插入值如上图所示:

#include <iostream>
#include <vector>
#include<string>
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));   //把str字符串中的子串按每次把头部减少一个的方式插入到vector向量中
 cout<<substrs[i]<<endl;//输出vector中的值 如上图
}

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))  //寻找以a开头的子串(对于本题的输入而言)下面依次为b开头的子串,一直到c开头的子串

     {

        ++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; //如果有连续一个子串出现就继续遍历vector的下一个子串中的和现在出现相同子串的地方的下一个或几个字符

        else   break;

        }

   if(count>maxcount)  //maxcount  记录所有遍历中的最大连续子串出现的次数

   {

     maxcount=count;

      substr=substrs[i].substr(0, j-i);

   }

       }//end if substrs[i].substr(0,j-i)

}//end for j

}//end for i

return make_pair(maxcount ,substr);   //把maxcount 和 找到的子串做成pair<>返回

}//end func

int main()
{
pair<int,string> result;
string str="abcbcbcabc";
result=fun(str);
cout<<result.first<<" "<<result.second<<endl; //输出为:2 ab
return 0;
}
 总体思路是:首先把给出的字符串按每次减少一个头部字符的方式存入vector中,然后开始在vector[0]中遍历以a开头的子串连续出现的次数。比较的方式为那vector[0]以a开头的一个字符和vector[1]内的比较 如果有 继续 没有 比较以ab开头的子串 。依次类推。下面是vector[1]中以b开头的的 步骤如上。

  评论这张
 
阅读(213)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018