/************************************************************************/
/* 利用后缀数组求解一个字符串中最长重复子串问题
例如asdfasdfa,其最长重复子串是asdfa
/************************************************************************/
#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';
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]);
return 0;
}