后缀数组求最大重复子串

#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 )//返回值必须是int，两个参数的类型必须都是const void * { return strcmp( *(char* const *)p1, *(char* const*)p2 ); //strcmp(s1，s2) 判断两个字符串s1和s2是否相同，相同返回ture ,不同返回false } 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,这样，每个元素就都指向输入字符串中的相应字符 { a[n]=&c[n];//数组a命名为"后缀数组 c[n++]=ch;//把ch的值赋值给a[n],然后n变成n+1 } c[n]='\0'; //将数组c中的最后一个元素设为空字符，以终止所有字符串。 qsort( a, n, sizeof(char*), pstrcmp );//对后缀数组进行快速排序，以将后缀相近的（变位词）子串集中在一起 //qsort包含在<stdlib.h>头文件中，此函数根据你给的比较条件进行快速排序，通过指针移动实现排序。 //排序之后的结果仍然放在原数组中。使用qsort函数必须自己写一个比较函数。第三个参数是单个元素的大小.第四个比较函数 for(i=0; i<n-1; ++i )//使用comlen函数对数组进行扫描比较邻接元素，以找出最长重复的字符串： { temp=comlen(a[i], a[i+1]); if( temp>maxlen) { maxlen=temp; maxi=i; } } printf("%.*s\n",maxlen, a[maxi]); system("PAUSE"); return 0; }