Codility - Gamma 2011 - count_palindromic 回文子串

这是一道Codility上的题目，见 https://codility.com/demo/take-sample-test/gamma2011/ 大意就是给定一个字符串，求出它的所有长度大于2的回文子串的个数。这与求字符串的最长回文子串的问题是等价的。

首先想到的就是遍历字符串的所有长度大于2的子串（共有2+3+...+n-1 = (n+1)(n-2)/2个），对每个子串判断是否为回文串，时间复杂度为O(n^3)

然后，我们注意到，所有的回文子串都有一个中心位置，而对于长为n的字符串，能作为回文子串中心位置的只有2n-1种可能（对于本问题，其实只有2n-3种可能，需要去除第一个和最后一个字符所在的位置），因此，只需遍历这些可能的位置，找出以该位置为中心的回文子串的数目，时间复杂度是O(n^2)。

看起来，似乎这种方法是最优的，毕竟，有2n-3个位置需要判断，而每次判断的时间复杂度是O(n)，因此最终时间复杂度是O(n^2)，看起来是不能再改善了。

但是呢，世界就是这么奇妙，就像神奇的KMP字符串匹配算法一样，居然能把字符串匹配的时间复杂度做到O(n+m)。对本问题，其实是存在O(n)时间复杂度的算法的！

为了统一处理奇数长度和偶数长度的回文串，我们在每个原字符串的每个字符之间加上一个分隔符#，并且在字符串开头加上一个终结符$，因此，当原字符串是baababa时，转换后的字符串是$#b#a#a#b#a#b#a#，这样，当回文中心是#字符时，回文长度为偶数；当回文中心不是#时，回文长度为奇数。

该算法的基本思想就是扫描处理后的字符串S，记录以每个字符为中心时的最长回文串，同时更新全局的最长回文串记录。描述如下：

待处理字符串为S，长度为N

P为长为n的数组，P[i]记录以字符i为中心的最长回文串的半边长度加1（回文串长度为 2*(P[i]-1) + 1）

K为之前的回文串到达的最右位置，j为该回文串的的中心位置

for i = 1..len(s)-1

    初始化P[i]

    逐渐增加P[i]，直至不满足回文串条件

    统计该回文串中回文数目

    if i+P[i] > K

        K = i + P[i]

        j = i

但看描述，似乎与O(n^2)的算法一样，但该算法的关键是初始化P[i]，如果每次循环之前P[i]能尽量大，那么每次循环的比较次数就很少，从而降低了复杂度。（具体时间复杂度分析比较复杂，本文不作精确分析）

那么如何确定一个较大的P[i]值呢？

不妨假设当前扫描到第i个字符，根据全局K和j值，我们有：

index            2j-i       j       i        K

char/str     A   S[i]  B  S[j]  B  S[i]  A  S[K]

由于以j为中心的回文串的最右位置为K（不包含），当K大于i的情况下，不妨假设i与K之间的字符串为A，j与i之间的字符串为B，那么根据回文串性质有2j-i与j之间字符串为B，2j-i之前存在字符串A。

可以利用2j-i与i位置的对称性，不妨假设P[2j-i] = x，那么说明B字符串的前x-1个字符与A字符串的后x-1个字符相同，因此对于i来说，只需要从i+x开始判断即可，如果i+x大于K，那么则从K开始递增。

具体代码（针对Codility题目）如下，亦可参见 https://github.com/phiphy/codility/blob/master/count_palindromic_slices.c

int imin(int x, int y) { return x < y ? x : y; }

int solution ( char *t ) {

    if (!t)

        return 0;

    int n = strlen(t);

    if (n < 2)

        return 0;

    int i, j, k, r = 0;

    int m = n + n + 3;

    char *s = (char *)malloc(sizeof(char) * m);

    int *p = (int *)malloc(sizeof(int) * m);

    for (s[0] = '$', s[1] = '#', i = 0, j = 2; i < n; ++i) {

        s[j++] = t[i];

        s[j++] = '#';

    }

    s[j] = '\0';

    for (k = 0, i = 1; i < m-1; ++i) {

        p[i] = k > i ? imin(p[2*j-i], k-i) : 1;  // update p[i], as large as possible

        while (s[i+p[i]] == s[i-p[i]])

            ++p[i];

        if (p[i] > 1) {

            r += (p[i]/2 - (s[i]!='#'));

            if (r > 100000000) {

                r = -1;

                break;

            }

        }

        if (p[i]+i > k) {

            k = p[i] + i;

            j = i;

        }

    }

    free(s); s = NULL;

    free(p); p = NULL;

    return r;

}

听说这道题也可以用后缀数组解决，不过我暂时还不懂后缀数组，这段时间研究一下。