HDU 6194 string string string

一眼以为KMP能解，上去就是一WA……

但是我还不知道KMP的错误点……可惜看不了提交的代码了……
这道题因为我在比赛的时候被一道煞笔树形DP卡到了，因为图没清空，所以没什么时间去看，虽然最后还是有一个小时给我，但我还是没有做出来。

比赛的时候天海的解法用到了单调栈，但我看了题解还有另一个非常巧妙的做法。

题意：
给你一个字符串，问你刚好出现 k 次的子串数量。

思路：
看了大佬的题解，只给了一个方程。枚举区间为 k – 1 的 height 数组，也就是 k 的 sa，贡献为

$ max(0, lcp( i , i + k – 1 ) – max(height[ i ], height[ i + k ]) $

一开始听蒙蔽的，略加思考就察觉到了方程的正确性，对于每个区间的 LCP ，如果跟区间外的后缀一旦有重复的，那么这个公共部分就不能算及在内。因为这个部分就不是刚好出现 k 次的子串了。于是把区间 LCP 将它减去即可。

注意 k == 1 的时候需要特判。

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int mmin[maxn][17], s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len - 1) s[i] = str[i] - 'a' + 1;
        s[len] = 0;
        DA(len + 1, 28);
        getHeight(len);
    }

    void initRMQ()
    {
        for (int i = 1; i <= len; i++)
            mmin[i][0] = height[i];
        for (int j = 1; (1 << j) <= len; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r)
    {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
    }

    void work(int k)
    {
        height[len + 1] = 0;
        int ans = 0;
        for (int i = 1; i <= len - k + 1; i++)
            ans += max(0, query(i, k) - max(height[i], height[i + k]));
        printf("%d\n", ans);
    }

    int query(int id, int k)
    {
        return k == 1 ? len - sa[id] : RMQ(id + 1, id + k - 1);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %s", &n, buf);
        suffix_array.input(buf);
        suffix_array.initRMQ();
        suffix_array.work(n);
    }
    return 0;
}