后缀数组之可重叠 k 次最长重复子串。
数据好水……他的 “ 字符 ” 范围为 [ 0 , 1e6 ]
按我最开始的想法,求后缀数组的时候,在字符最大值超过 char 我就打算用 sort 代替基数排序了。
然而……直接取最大值用基数排序居然过了,还是 63 ms ……

下面是可重叠 k 次最长重复子串的求法:
解法与不可重叠最长重复子串的做法基本一致。
二分答案,将排序后的后缀按照二分值分成若干组,如果某一组的数量大于等于 k ,那么这个二分值是可行值。

题意:
可重叠 k 次最长重复子串。

思路:
见上。

AC Code

#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 = 2e4 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int 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(int n)
    {
        len = n;
        int maxx = 0;
        each(i, n)
        {
            scanf("%d", s + i);
            maxx = max(maxx, s[i]);
        }
        s[len] = 0;
        DA(len + 1, maxx + 1);
        getHeight(len);
    }

    bool check(int key, int k)
    {
        int cnt = 1;
        range(i, 2, len) if (height[i] >= key)
        {
            if (++cnt >= k)
                return true;
        }
        else cnt = 1;
        return cnt >= k;
    }

} suffix_array;

int main()
{
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF) {
        suffix_array.input(n);
        int l = 0, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (suffix_array.check(mid, k))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    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…