最长重复子串问题

slg_sparkler 2007-10-02 10:41:32

想要把一个字符串中重复最长的部分提取出来，比如说有如下字符串：
abcdbcdbcb
对于这个字符串最长的重复子串为bcdbc!

...全文

2976 19 打赏收藏转发到动态举报

写回复

用AI写文章

19 条回复

切换为时间正序

请发表友善的回复…

发表回复

luo6620378xu 2012-04-25

打赏
举报

[Quote=引用 1 楼的回复:]

可以用后缀树来做。

贴一下代码：
C/C++ code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXCHAR 5000 //最长处理5000个字符

char c[MAXCHAR], *a[MAXCHAR];

int comlen( char *p, char *q ){
int……
[/Quote]
这个代码应该有问题才对，这样排序字符串是不行的。
你这里贴的完全是《编程珠玑》上的源码。

DeDeWo 2012-04-08

打赏
举报



#include<iostream>

#include<cstring>

using namespace std;

const int MM=100000;

int next[MM];

char str[MM];

void GetNext(char *t){

     int len=strlen(t);

     next[0]=-1;

     int i=0,j=next[i];

     while(i<len){

         if(j==-1 || t[i]==t[j]){

             i++;

             j++;

             next[i]=j;

         }

         else

             j=next[j];

     }

}

int main(){

    int index,len;

    while(cin>>str){

       char *s=str;

       len=0;

       for(int i=0;*s!='\0';s++,i++){

           GetNext(s);

           for(int j=1;j<=strlen(s);j++)

               if(next[j]>len){

                    len=next[j];

                    index=i+j; //index是第一个最长重复串在str中的位置 

               }

       }

       if(len>0){

          for(int i=index-len;i<index;i++)

             cout<<str[i];

          cout<<endl;

       }

       else

           cout<<"none"<<endl;

    }

return 0;

}

DeDeWo 2012-04-08

打赏
举报

刚写了一个,总感觉next数组效率低，不管了，贴上

#include<iostream>
#include<cstring>
using namespace std;
const int MM=1000000;
int next[MM];
char str[MM];
void GetNext(char *t){
int len=strlen(t);
next[0]=-1;
int i=0,j=next[i];
while(i<len){
if(j==-1 || t[i]==t[j]){
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int main(){
int index,len;
while(cin>>str){
char *s=str;
len=0;
for(int i=0;*s!='\0';s++,i++){
GetNext(s);
for(int j=1;j<=strlen(s);j++)
if(next[j]>len){
len=next[j];
index=i+j; //index是第一个最长重复串在str中的位置
}
}
if(len>0){
for(int i=index-len;i<index;i++)
cout<<str[i];
cout<<endl;
}
else
cout<<"none"<<endl;
}
return 0;
}

baiyizhujian 2012-04-01

打赏
举报

顶一下

qiuxi824039983 2012-03-29

打赏
举报

用next函数值也可以吧

CHZiroy 2012-03-27

打赏
举报

今晚解决这道题

nolan218 2008-10-05

打赏
举报

学习

Super.Jiju 2008-08-29

打赏
举报

http://super-jiju.spaces.live.com/blog/cns!806C498DDEE76B61!270.entry

#include <iostream>

#include <string>

using namespace std;



int lcs(string A,string B);

int c[100][100]={0};

int b[100][100]={0};

void image(int i,int j,string &A);

int main()

{

    string a,b;

    cin>>a>>b;

    if(a.length()>100 || b.length()>100)

    {

        cerr<<"Can not get the lcs of the string which length over 100"<<endl;

        exit(0);

    }

    string &aa=a;

    cout<<"\n"<<endl;

    lcs(a,b);

    cout<<"\n"<<endl;

    image(a.length(),b.length(),aa);   

    cout<<endl;

    system("pause");

    return 0;

}



int lcs(string A,string B)

{

    int    mA=A.length();

    int nB=B.length();



    int len=0;

    for(int i=1;i<=mA;++i)

    {

        for(int j=1;j<=nB;++j)

        {

            if(A.at(i-1)==B.at(j-1))

            {

                c[i][j]=c[i-1][j-1]+1;

                len++;

                b[i][j]=3;

            }

            else if(c[i-1][j]>=c[i][j-1])

            {

                c[i][j]=c[i-1][j];

                b[i][j]=1;

            }

            else

            {

                c[i][j]=c[i][j-1];

                b[i][j]=2;

            }

        }

    }



    //-----image the road

    for(int j=1;j<=nB;++j)

    {

        cout<<"\t"<<B.at(j-1);

    }

    cout<<endl;

    for(int i=1;i<=mA;++i)

    {

        cout<<A.at(i-1)<<"\t";

        for(int j=1;j<=nB;++j)

        {

            cout<<b[i][j]<<"\t";

        }

        cout<<"\n"<<endl;

    }



    return len;



}

void image(int i,int j,string &A)

{



    //-----3:up and left,1:up,2:left

    if(i==0||j==0)

        return;

    if (b[i][j]==3)

    {

        cout<<A.at(i-1)<<"\t";

        image(i-1,j-1,A);       

    }



    if(b[i][j]==1)

        image(i-1,j,A);

    if(b[i][j]==2)

        image(i,j-1,A);

}

boxer_tony 2008-08-29

打赏
举报

8楼的算法似乎还存在一些问题：
当src为&input[1]时，dest分别取&input[4,7,9]
但这样还不够，还应该分别考虑src为input[4,7,9]时的情形

ddfjdkt 2008-08-29

打赏
举报

楼上找的是两个字符串的公共子串吧

kulou1087 2008-06-08

打赏
举报

MARK TO STUDY

jmulxg 2008-05-20

打赏
举报

假设有26个字符a-z
遍历数组，建立26个数组，分别保存a-z所在的位置下标
比如input[max]="abcdbcdbcb";
那么数组a[1]={0};
b[4]={1,4,7,9};
c[3]={2,5,8};
d[2]={3,6};

再次遍历数组input
input[0]='a',因为数组a只有一个字符，故没有与之重复的字符串；
input[1]='b',与之重复的字符串开始下标为b[1]=4,
开始比较重复字符串长度length（当然可获取重复的字符串）
假设指针src=&input[1],dest=&input[4]
步骤一、while(*src==*dest)
{src++;dest++;length++;}

然后 dest=&input[7]再执行步骤一
dest=&input[9]执行步骤一

input[2]
....
input[9]

遍历一次数组input可获得最长重复子串

食人族哲学家 2008-05-19

打赏
举报

有空来看看

diaoxue 2008-05-18

打赏
举报

后缀树/后缀数组?

wzcsoft 2008-05-17

打赏
举报

楼上正解，那段代码网上到处都是，用的是后缀数组，not后缀树。

zsdlightning 2008-03-05

打赏
举报

首先，你用的不是后缀树，其次你的算法效率很低，是高于n^2的，不要以为字符串比较不花时间

c_primer_ 2007-10-04

打赏
举报

mark for stud

medie2005 2007-10-03

打赏
举报

可以用后缀树来做。

贴一下代码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>



#define MAXCHAR 5000 //最长处理5000个字符



char c[MAXCHAR], *a[MAXCHAR];



int comlen( char *p, char *q ){

    int i = 0;

    while( *p && (*p++ == *q++) )

        ++i;

    return i;

}



int pstrcmp( const void *p1, const void *p2 ){

    return strcmp( *(char* const *)p1, *(char* const*)p2 );

}



int main(  ){

    char ch;

    int  n=0;

    int  i, temp;

    int  maxlen=0, maxi=0;

    printf("Please input your string:\n");

    while( (ch=getchar())!='\n' ){

        a[n]=&c[n];

        c[n++]=ch;

    }

    c[n]='\0';

    qsort( a, n, sizeof(char*), pstrcmp );

    for(i=0; i<n-1; ++i ){

        temp=comlen( a[i], a[i+1] );

        if( temp>maxlen ){

            maxlen=temp;

            maxi=i;

        }

    }

    printf("%.*s\n",maxlen, a[maxi]);

    system("PAUSE");

    return 0;

}