【编程珠玑】第十五章字符串（二）

水深无声 2022-09-24 11:23 213阅读 0赞

给定一个文本作为输入，找出其中最长的重复字符串  
（1）查看所有字符串，并依次进行比较：

for i= [1,n)
        for j=[i,)
            if (thielen=comlen(&c[i],&c[j])) > maxlen
                maxlen = thielen;
                maxi = i;
                maxj = j;

思路十分简单，不过由于查找所有字符串对，因此时间最少为n\*n的倍数。  
（2）使用“后缀数组”的思想，先求出输入字符串的所有后缀数组，然后对后缀数组进行排序，再在相邻的后缀数组间寻找相同字符的个数：

#include <stdlib.h>  
    #include <string.h>  
    #include <stdio.h>  
    
    #define M 1  
    #define MAXN 5000000  
    char c[MAXN], *a[MAXN];
    
    int pstrcmp(char **p, char **q)
    {
        return strcmp(*p, *q);
    }//两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇'\0'为止。  
    
    int comlen(char *p, char *q)
    {
        int i = 0;
        while (*p && (*p++ == *q++))
            i++;
        return i;
    }
    
    int main()
    {
        int i, ch, n = 0, maxi, maxlen = -1;
        while ((ch = getchar()) != EOF) {
            a[n] = &c[n];
            c[n++] = ch;
        }
        c[n] = 0;
    
        qsort(a, n, sizeof(char *), pstrcmp);//快速排序   
        for (i = 0; i < n - M; i++)
            if (comlen(a[i], a[i + M]) > maxlen) {
       //比较相邻字符串相同个数   
                maxlen = comlen(a[i], a[i + M]);
                maxi = i;
            }
        printf("%.*s\n", maxlen, a[maxi]);//使用*精度
        return 0;
    }

运行结果举例：  
![这里写图片描述][20160729193902515]  
由于排序的存在，算法的运行时间为O(nlogn)。

[20160729193902515]: /images/20220719/173655c9598c46c1b251f17cf77aad50.png