C++面试题算法

#include <iostream>

#include <string>

using namespace std ;

/*

题目：给一个字符串、例如 “ababc”要求返回“ab”. 因为“ab”连续重复出现且最长。

用C/C＋＋语言写一函数完成该算法，给出复杂度

这道题的最终目的是找到最长的连续字符串

*/

struct SubStringInfo

{

 int maxSubStrLength ;//最长字符串的长度

 string str ;//最长字符串

}strData;

bool Check(string &str,string substr) //检测某字符串是否连续

 int pre ; //前串

 int next;//后串

 if(str.length()==substr.length())

  return false ;

 pre=str.find(substr);  //查找字符串出现的位置

 if(pre==-1) return false; //如果找不到那么返回 string::npos到头  -1

 next=str.find(substr,pre+substr.length());

 if(next==pre+substr.length())

  return true ; 

 return false;

}

void SearchString(SubStringInfo &info,string &str)

 int len=str.length() ;//获取string长度 

 string  eachMaxString="";

 string  tem="";

 bool ret=false ;

 int index=0 ;

 for(int i=1;i<=len;i++)  //每个子串长度

 {  

  index=0;

  cout<<"Sub String Length:"<<i<<": "<<endl ;

  for(int j=len-i+1;j>0;j--)//该长度的子字符串有多少个

  {    

   tem=str.substr(index,i);//获取子字符串

   cout<<"index="<<index<<" "<<"i="<<i<<" "<<tem<<" " ;

   index++;

   ret=Check(str,tem) ;//检测

   if(ret)

   {  

    if(tem.length()>info.maxSubStrLength)

    {

     info.maxSubStrLength=tem.length() ;//保存长度

     info.str=tem ;

    }

   } 

  }

  cout<<"\n";

 }

void main()

{    

    strData.maxSubStrLength=0;  //初始化结构体

 strData.str="";

 string  str ;  //接受要输入的字符串 

 cout<<"输入字符串:"<<endl ;

 cin>>str ;    

 SearchString(strData,str) ;//搜索字符串

 cout<<"最长的连续字符串为:"<<strData.str<<endl;