#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;
}