最大公子串问题

问题：设一个字符串，求一最大公有子串，使得该子串在字符串的头部和尾部都存在，且是最长的。

 

分析：记该字符串为a = a[1]a[2]...a[n],
      数组len = len[1]len[2]...len[n], 代表前i个字符所组成的最大公有子串的长度;
      比如，len[5]，就表示前5个字符所组成的串的最大公有子串的长度。
      如果不存在最大公有子串，那么len[i]=0，且记len[1]=0
      那么如何求得len[i](1      记k=len[i-1]
      如果a[k+1]=a[i]，那么显然，len[i]=k+1;
      如果a[k+1]!=a[i]，那么len[i]或者大于k+1, 或者小于k+1
      假如len[i]>k+1, 那就意味着len[i-1]>k，这是不可能的
      所以只有可能是len[i]      现在假设该最大公有子串长度为x+1，那么可以证明串a[1..x]是串a[1..k]的一个公有子串
      事实上，因为a[1..x]=a[i-x..i-1], 而a[i-x..i-1]=a[k-x+1..k]
      从而，有a[1..x]=a[k-x+1..k]，所以串a[1..x]是串a[1..k]的一个公有子串
      知道了这一点，就意味着如果存在最大公有子串，
      那么该公有子串一定是串a[1..k]中的公有子串再接一个字符a[i]
      所以我们可以从串a[1..k]的最大公有子串找起，一直往回找，直到找到或不存在为止。

 

算法设计与实现：

输入：字符串pattern

输出：一个整数数组，与pattern同长度， 其第i个值代表pattern前i个字符所组成的最大公有子串的长度

int *compute_prefix(const char *pattern) {
    int *prefix;
    int i, k, size;

    assert(pattern);
    size = strlen(pattern);
    prefix = malloc(size * sizeof(int));
    memset(prefix, '\0', size * sizeof(int));
    for (i = 1; i < size; i++) {
        k = prefix[i-1];
        while (1) {
            if (pattern[i] == pattern[k]) {
                prefix[i] = k+1;
                break;
            }
            if (k == 0) break;
            k = prefix[k-1];
        }
    }
    return prefix;
}

此算法是实现kmp模式匹配的基础