求最长重复字串 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：6

求最长重复字串

一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca，结果是bc。

搜索更多相关主题的帖子: 字串　

第 2 楼

得分:3

#include <stdio.h>
#include <string.h>

char str[100];
char ch[10];

void insert(int start,char *ch,int size);

void main(){
    int num=0;
    int StartFirst=0,StartSecond=0,TempWordSize,WordSize=0;
    printf("Please input :");
    gets(str);
    for(char *Str=str;*Str!='\0';num++,Str++)
        ;
    for(;(StartFirst+2*WordSize+1)<num;StartFirst++){
        StartSecond=StartFirst+WordSize+1;
        for(;(StartSecond+WordSize)<=num;StartSecond++){
            TempWordSize=0;
            for(;str[StartFirst+TempWordSize]==str[StartSecond+TempWordSize]&&StartFirst+TempWordSize<StartSecond;TempWordSize++)
                ;
            if(TempWordSize>=WordSize){
                WordSize=TempWordSize;
                insert(StartFirst,ch,WordSize);
            }
        }
    }
    if(WordSize==0)
        printf("NO\n");
    else{
        printf("%d\n",WordSize);
        puts(ch);
    }
}

void insert(int start,char *ch,int size){
    for(int num=0;num<size;num++,start++,ch++)
        *ch=*(str+start);
}

最笨的方法~~
不知道大侠们有没有什么更好的办法，拿出来分享一下嘛~

第 3 楼

得分:3

看的头疼说下你的思路就可以了

第 4 楼

得分:3

2楼的效率比较低如果利用后缀数组实现，o(nlogn)~~~~ 就能实现了·····详细可以见下面的链接··

http://blog.

据说o(n)就可以搞定。。。有难度！期待高手出现····

第 5 楼

得分:3

同样期待

人生就像茶几　上面放着许多杯具

人生也像厨房　里面总有一些洗具

第 6 楼

得分:0

可以用动态规划法实现，效率很好

参看　生物领域的 blast 的实现方法

人生就像茶几　上面放着许多杯具

人生也像厨房　里面总有一些洗具

第 7 楼

得分:0

中午有时间写了一下这个程序，是我想到的效率最高的一种了(也就是前面说的blast的算法）

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(a,b) (a>b?b:a)
#define MAXCHAR 10000
int main (int argc,char **argv)
{
    char *c = (char *)malloc(MAXCHAR*sizeof(char));
    char *bestchar;
    int bestmatch[2]={0,0};
    int beststep,step,maxstep;
    int i,j;
    int len;

    printf("Pleas input the string:\n");
    gets(c);
    len = strlen(c);

    //get best match
    for (i=0;i<len ;i++ )
        for (j=i+1;j<len ;j++ )
        {
            if (c[i] == c[j])
            {
                step = 1;
                maxstep = MIN(len-i,len-j);

                while(step<maxstep && c[i+step]==c[j+step]) step++;
   
                if (bestmatch[1]<step)
                {
                    bestmatch[0] = i;
                    bestmatch[1] = step;
                }
            }
        }

    //copy best match to bestchar
    bestchar = (char *)malloc(bestmatch[1]*sizeof(char));
    for (i=0;i<bestmatch[1] ;i++ ) bestchar[i] = c[i+bestmatch[0]];
    bestchar[i]='\0';

    printf("The longest copied string is %s\n",bestchar);

    free(bestchar);
    free(c);
}

应该可以结题了

人生就像茶几　上面放着许多杯具

人生也像厨房　里面总有一些洗具