百度之星H题pair！pair！解决办法

百度之星H题pair！pair！！！
描述
馅饼同学是一个在百度工作，做用户请求（query）分析的同学，他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”，这些词汇虽然看起来是一些词汇的单纯重复，但是往往都是一些特殊品牌的词汇，不能被拆分开。为了侦测出这种词的存在，你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。

输入
输入数据包括多组，每组为一个全部由小写字母组成的不含空格的用户请求（字符串），占一行。用户请求的长度不大于100,000。
最后一行输入为#，作为结束的标志。
输出
对于每组输入，先输出这个组的编号（第n组就是输出“Case n:”）；然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串，请选择那个字典序最小的。
样例输入
ilovejohnsonjohnsonverymuch
duckduckgo
aaabbbcccisagoodcompany
#
样例输出
Case 1: johnsonjohnson
Case 2: duckduck
Case 3: aaa
*************************************************************
以下是我的代码：

C/C++ code


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

pair<int,string> fun(const string &str)
{
vector<string> substrs;
int maxcount=1,count=1;
string sub;
int i,len=str.length();
for(i=0;i<len;i++)
{
 substrs.push_back(str.substr(i,len-i));   //把str字符串中的子串按每次把头部减少一个的方式插入到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;
            sub=substrs[i].substr(0, j-i);
        }
         else if(count==maxcount&&strncmp(sub.c_str(), substrs[i].c_str(), count)>0)
         {
            maxcount=count;
            sub=substrs[i].substr(0, j-i);
         }
      }
      
}
}
if(sub=="\0")
      {
          sub=substrs[0];
          char ch='z';
          for(int k=0;k<len;k++)
          {
              if(sub[k]<ch)
                  ch=sub[k];
          }
          sub=ch+'\0';
      }
return make_pair(maxcount ,sub);   //把maxcount 和 找到的子串做成pair<>返回
}
int main()
{
    int i=1;
pair<int,string> result;
string str;
while(getline(cin,str)&&str!="#")
{
    cout<<"Case "<<i++<<": ";
    result=fun(str);
    for(int j=0;j!=result.first;j++)
    {
        cout<<result.second;
    }
    cout<<endl;
}

return 0;
}

一直编译错误，返回的信息是：1157530.8486/Main.cc: In function ‘std::pair<int, std::basic_string<char, std::char_traits<char>, std::allocator<char> > > fun(const std::string
求大神解答。。。

------解决方案--------------------
#include <cstring>
------解决方案--------------------
思路和我一致，结果是超时
------解决方案--------------------
要用rmq优化。不然超时的。
------解决方案--------------------
这个题明显是用后缀树组来做，直接套模板
------解决方案--------------------
不懂啊
------解决方案--------------------
输入空字符串后出错。。。

百度之星H题pair！pair！解决办法

相关推荐