问题描述：
给定一个文本文件作为输入，查找其中的最长子字符串。例如， ”Ask not what your country can do for you, but what you can do for your country"中的“ can do for you"就是最长子字符串。
解题过程：
这个问题最直接的解法就是变位词程序（《编程珠玑》2.4节）。如果将输入字符串存储在c[0..n-1]中，那么我们可能会使用类似下面的伪代码比较每个子串；
maxlen = -1; for i = [0, n] for j = (i, n) if (thislen = comlen(&c[i], &c[j])) > maxlen maxlen = thislen; maxi = i; maxj = j;
comlen函数返回其两个参数字符串中共同部分的长度，从第一个字符开始比较：
int comlen(char* p, char* q) { int i = 0; while (*q && (*p++ == *q++)) { i++; } return i; }
该算法需要的时间复杂度为o(n^2)。可以用散列表搜索短语中的单词来实现提速，但是这里有另一个跟好的算法：
我们将使用“后缀数组”的简单简单结构。
#define MAXN 50000 char c[MAXN]; char* a[MAXN]; char ch; int n = 0; while ((ch = getchar()) != EOF) { a[n] = &c[n]; c[n++] = ch; } c[n] = 0;
如果c中存储的是“banana”，该数组的后缀数组内容就是：
a[0] = "banana"
a[1] = "anana"
a[2] = "nana"
……
然后对其进行排序，可以使用qsort来进行，对排序完的数组只需要一边扫描，统计相邻单词共有子串的长度。
思路就是这样，完整的代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 50000 int comlen(char* p, char* q) { int i = 0; while (*q && (*p++ == *q++)) { i++; } return i; } int cstring_cmp(const void *a, const void *b) { const char **ia = (const char **)a; const char **ib = (const char **)b; return strcmp(*ia, *ib); } int main() { char c[MAXN]; char* a[MAXN]; char ch; int n = 0; while ((ch = getchar()) != EOF) { a[n] = &c[n]; c[n++] = ch; } c[n] = 0; qsort(a, n, sizeof(char*), cstring_cmp); int maxlen = 0; int len = 0; int maxi = 0; for (int i = 0; i < n - 1; i++) { len = comlen(a[i], a[i + 1]); if (len > maxlen) { maxlen = len; maxi = i; } } printf("maxlen:%d\tmax string:\t", maxlen); char ch_tmp; for (int i = 0; i < maxlen; i++) { ch_tmp = *(a[maxi] + i); printf("%c", ch_tmp); } printf("\n"); return 0; }
本文转自博客园知识天地的博客，原文链接：后缀树求最长子字符串，如需转载请自行联系原博主。
