查找出现M次的最长的字符串

    该问题来源于《编程珠玑》，解决的思想是用后缀数组，代码如下所示。

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* longdup.c -- Print longest string duplicated M times */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int pstrcmp(char **p, char **q)
{
    return strcmp(*p, *q);
}

int comlen(char *p, char *q)
{    int i = 0;
    while (*p && (*p++ == *q++))
        i++;
    return i;
}

#define M 2            //超过次数
#define MAXN 5000000
char c[MAXN], *a[MAXN];

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("%.*sn", maxlen, a[maxi]);
    return 0;
}

    思路是这样的：数组a是一个指针数组，子数组a[i...i + M]表示M+1个字符串。由于数组是有序的，可以通过在第一个字符串i和最后一个字符串i+M上调用comlen函数快速确定这M+1个字符串共有的字符数目。