- // 求字符串中最长重复字串并输出其长度
- // 解题思路,从第一个字符开始匹配,若匹配成功,则并入下一个字符继续匹配,
- // 若匹配失败,当为单个字符时,以下一个字符为第一个字符进行循环匹配,否则
- // 以当前字符为第一个字符进行循环匹配
- #include<iostream>
- #include<string>
- using namespace std;
- int pipei(string &,string &,int );
- using namespace std;
- void main(){
- string s;int n=0;string STR; //STR存储当前最长的字符串
- cin>>s;
- string str="";
- str=str+s[0];
- for(int i=0;i<s.size()-1;){
- if(int now=pipei(s,str,i+1)){ //匹配成功
- do{
- int start=now-str.size(); //匹配成功则尽可能多的并入字符
- i=i+1;
- //例如abcdefghhhh与后面的abcdefg当发现a匹配上后则可以并入为abcdefgh,
- //再在后面查找是否有abcdefgh串,可提高运算速度
- for(;i<start&&now<s.size()&&s[i]==s[now];i++,now++)
- str+=s[i];
- if(str.size()>n){
- STR=str;
- n=STR.size();
- }
- str+=s[i];
- }while(now=pipei(s,str,now));
- }
- else{ //匹配失败
- if(str.size()==1){
- i++;
- // str=s[i];
- }
- str=s[i];
- }
- }
- cout<<n<<endl;
- cout<<STR;
- getchar();
- getchar();
- getchar();
- }
- int pipei(string &s1,string &s2,int i){
- int j=0;
- while(i<s1.size()&&j<s2.size()){
- if(s1[i]==s2[j]){
- ++i;
- ++j;
- }
- else{
- i=i-j+1;
- j=0;
- }
- if(j==s2.size())
- return i; //返回当前的位置
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/231020136602.html
来源: http://www.codesnippet.cn/detail/231020136602.html