HDU 4552 怪盗基德的挑战书

一道不知所以然的题目……

没什么好废话的，直接上题解。

题意：
要你求一个字符串的所有前缀在自己本身的所有出现次数。

思路：
这道题如果用KMP的话是十分简单的，但是我一开始没想到用KMP，想了一些时间，看了kuangbin的博客说可以用KMP求解，略想了一下，果真如此。

KMP思路：
直接next数组跳几下就可以了。

后缀数组思路：
后缀数组的思路让我有点蒙逼……只要将所有后缀与最长的后缀，也就是原串的最长公共前缀相加再加上原串长度就是答案。
而看过论文的都应该知道，这个是可以( O( n ) )直接求出来的。
但是还是有点似董非董。

#include <bits/stdc++.h>

#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;

const int maxn = 1e5 + 5;
int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m) //n取字符串长度+1 m为字符中的上界 一般为 128
{ 
    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 s[], int n) //n为字符串长度
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

char str[maxn];
int s[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int t = rnk[0], ans = len, tmp = len;
        while (t > 1) {
            tmp = min(tmp, height[t--]);
            ans += tmp;
        }
        t = rnk[0] + 1, tmp = len;
        while (t <= len) {
            tmp = min(tmp, height[t++]);
            ans += tmp;
        }
        printf("%d\n", ans % 256);
    }
    return 0;
}