最长重复字串 后缀数组解法

可重叠最长重复子串
  这个就是后缀数组里，max{lcs(a[i],a[i+1])}就是最长公共前缀,这个最长重复字串,blog以前是用KMP的那种思路写 的

 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.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';
    for(i=0;i<n;i++)
     printf("%d:%s\n", i+1, a[i]);
     
    qsort(a, n, sizeof(char*), pstrcmp);
    for(i=0;i<n;i++)
     printf("%d:%s\n", i+1, a[i]);
    
    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;
}