后缀数组

POJ 3693 Maximum repetition substring

后缀数组之重复次数最多的连续重复子串
这道题真的是做的我脑壳疼……
口误,根本不能算是做,死嗑论文怎么也嗑不出来……

好难,这应该是我现在做过的后缀数组里最难的一题了……

这里放上我理解之后的思路:
首先枚举长度 l ,如果存在两个长度为 l 的连续重复子串,那么在 \( str[ 0 ] , str[ l ] , str[ l \times 2 ] \) …… 中必然会存在两个相邻的位置他们值相同(加上这个优化,速度可以大幅度提升),我们对这两个位置的后缀求最长公共前缀 lcp ,那么显然,由这两个位置得出的子串重复次数为 \( lcp \div l + 1 \)。
但是这个答案并不一定是正确的,因为我们只能确保 \( str[ 0 ] , str [ l ] , str[ l \times 2 ] \) …… 中会出现重复值,但是这几个是边界。
由kuangbin大佬给出一个想法是考虑 \( lcp \% l \) 的含义。\( lcp \% l \) 是代表着对于 某个长度为 l 的连续子串 s ,被截断在右侧的长度为 \( lcp \% l \) ,那么被截断在左侧的长度便是 \( l - lcp \% l \)。
那么这个子串 s 的实际左边界就是 我们枚举的 \( i - ( l - lcp \% l ) \) ,因此右侧为 \( i - ( l - lcp \% l ) + l \) 。由这个区间求出的 lcp 如果仍然大于等于 原先的 lcp ,那么就需要使得重复次数 + 1 。
然后我们根据最大重复次数记录每个可重复子串的长度。(因为我们要求的是重复次数最多,重复长度无关紧要)。
最后我们要求的是字典序最小的,所以我们只要根据后缀数组一一枚举判断即可。

题意:
求重复次数最多的连续重复子串,若有多个结果,输出字典序最小的那个。

思路:
见上。

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 = 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]);
    }

    int lcp(int a, int l)
    {
        if (a == l)
            return len - a;
        int u = rank[a], v = rank[l];
        return u > v ? RMQ(v + 1, u) : RMQ(u + 1, v);
    }

    int ans[maxn];
    void work(char* str, int cas)
    {
        int maxx = 0, cnt = 0;
        range(l, 1, len - 1) for (int i = 0; i + l < len; i += l)
        {
            if (str[i] != str[i + l])
                continue;
            int k = lcp(i, i + l), num = k / l + 1;
            int pre = i - (l - k % l);
            if (pre >= 0 && k % l) {
                if (lcp(pre, pre + l) >= k)
                    num++;
            }
            if (num > maxx) {
                maxx = num;
                cnt = 0;
                ans[cnt++] = l;
            } else if (num == maxx)
                ans[cnt++] = l;
        }
        cnt = unique(ans, ans + cnt) - ans;
        int key = -1, st = 0;
        range(i, 1, len)
        {
            each(j, cnt) if (lcp(sa[i], sa[i] + ans[j]) >= (maxx - 1) * ans[j])
            {
                key = ans[j];
                st = sa[i];
                break;
            }
            if (~key)
                break;
        }
        str[st + key * maxx] = '\0';
        printf("Case %d: %s\n", cas, str + st);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int cas = 0;
    while (scanf("%s", buf) != EOF && buf[0] != '#') {
        suffix_array.input(buf);
        suffix_array.initRMQ();
        suffix_array.work(buf, ++cas);
    }
    return 0;
}

发表评论

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