后缀数组之最长公共前缀的不定查询。
因为查询很多,所以要结合RMQ算法。这个也是很简单的,一般不会有什么变化,只要套一下木板就好了。

但是这个有一个非常困扰我的地方,就是题目给定的查询不是后缀之间的最长公共前缀查询,而是子串之间的查询,这可难倒我了,我也不知道该如何解决。

看了题解后,发现其实解决方法很简单,只要将求得的 LCP 与两个子串长度互相比较,三个长度取最小就是我们要得答案。

题意:
给你一个字符串,再给你很多子串,要你将所有给定的子串进行压缩。
压缩方式为将两个字符串的最长公共前缀在第二个字符串用数字表示。

输出未压缩的长度和压缩后的长度,要记空格和换行。

思路:
不断求 LCP 即可。
在求的过程中有几个注意的地方。

  • 注意后缀相同的情况。
  • 得到两个后缀的 rank 后不能直接使用 RMQ ,一方面有不确定的大小关系,另一方面,我们是对height 数组求 RMQ ,做区间应为 较小的 rank + 1 。
  • 注意将RMQ数组开大……

这道题使用的代码已经能成为我求 LCP 的模板了 除了改成DC3

AC Code

#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;
typedef long long ll;
const int maxn = 1e5 + 5;

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) s[i] = str[i];
        DA(len + 1, 128);
        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);
    }

} suffix_array;

char str[maxn];

int calc(int val)
{
    int ret = 1;
    while (val > 9) {
        val /= 10;
        ret++;
    }
    return ret;
}

int main()
{
    int qn, pl, pr, l, r;
    while (scanf("%s", str) != EOF) {
        suffix_array.input(str);
        suffix_array.initRMQ();
        scanf("%d %d %d", &qn, &pl, &pr);
        ll lans = pr - pl + 1, rans = pr - pl + 3;
        qn--;
        while (qn--) {
            scanf("%d %d", &l, &r);
            int lcp = suffix_array.lcp(pl, l);
            lcp = min(lcp, min(pr - pl, r - l));
            lans += r - l + 1;
            rans += r - l + 2 - lcp + calc(lcp);
            pl = l, pr = r;
        }
        printf("%lld %lld\n", lans, rans);
    }
    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…