最长重复字串

ubuntuer

eg:
  input aabcdabcde
  output abcd

首先懂kmp的请回顾下kmp的next数组的求法,不懂得话就去自己看看
   a  a  b  c  d  a  b  c  d  e
  -1  0  1  0  0  0  1  0  0  0
大家也许就说了这有麽用呢...对是没用
   a  b  c  d  a  b  c  d  e
  -1  0  0  0  0  1  2  3  4

  ok看到没,如果是下面这样情况的话就可以了....


第一种情况,只要i++就可以变成二了....主要的循环就是
for(i=0;i
   然后对str+i,求next,在找出最大的next[],如果max
大家也许对这里的i

看下intput: aaa
这样的直接一次循环就搞定了,当然这里会有点小问题如果输入aba的


如果是abcabc,最后还必须加1,废话了这么多,也许还是直接看程序易懂些


#include stdio.h>
#include stdlib.h>
int kmp_next(char* s, int next[])
{
  int i = 0;
  int k = -1;
  int len = strlen(s);
  
  next = k;
  while(ilen-1)
   {
     if(k==-1 || s==s[k])
      {
        i++;
        k++;
        next = k;
      }
     else
      k = next[k];
   }
}
int find_kmp_max(int next[], int n, int* index)
{
   int max = next[0];
   while(n>0)
    {
      if(next[n-1]>max)
       {
        *index = n;
        max = next[n-1];
        }
       n--;
    }
  return max;
}
int getmax_substr(char* str, int* pos, int* max_sub_len)
{
   int len = strlen(str);
   int max = 0;
   int i;
   int index;
   int* next = (int*)malloc(sizeof(int)*len);
   
   *max_sub_len = 0;
   for(i=0;ilen-2;i++)
    {
      kmp_next(str+i, next);
      max = find_kmp_max( next, len-i, &index);
      if(max>*max_sub_len)
       {
        *max_sub_len = max;
        //if(index == len)
        if((index == len) && (*(str+len-1) == *(str+i+max)))
          *max_sub_len += 1;
        
        *pos = i+1;
       }
    }
   free(next);
}
  
int main(int argc, char *argv[])
{
  //char* str = "aabcdabcde";
  char* str = "aba";
  int pos = 0;
  int max_sub_len = 0;
  int i;
   
  getmax_substr(str, &pos, &max_sub_len);
  printf("str is:%s\npos is %d, max_sub_len is %d\n",str,pos,max_sub_len);
  
  for(i=0;imax_sub_len;i++)
     printf("%c",str[i+pos-1]);
  
  printf("\n");
  system("PAUSE");   
  return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_2025469.html