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

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

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

思路:
这道题如果用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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

后缀数组

POJ 3415 Common Substrings

后缀数组 + 单调栈好题 网络赛时的后缀数组可以用这个思路解,但是我并 Read more…

后缀数组

HDU 6194 string string string

一眼以为KMP能解,上去就是一WA…… 但是我还不知道KMP的错误点… Read more…

后缀数组

POJ 3693 Maximum repetition substring

后缀数组之重复次数最多的连续重复子串 这道题真的是做的我脑壳疼…… 口 Read more…