程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++面試題算法

C++面試題算法

編輯: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;
}

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved