后缀数组

POJ 3415 Common Substrings

Posted on

后缀数组 + 单调栈好题
网络赛时的后缀数组可以用这个思路解,但是我并不是很会,今天补上。

题意:
给你两个串,问你长度不小于 k 的重复子串的数量。

思路:
若只是对于一个字符串,问它长度不小于 k 的重复子串数量,那么考虑对height根据 k 分组,然后记录一下就可以了,将 height 去重后,每个 height 的贡献为 \( max ( 0, height - k +1 ) \) 个人猜测,后果不计

但这题是两个字符串,我们可以将两个字符串用一个特殊字符连接,并将后缀通过第一个字符串长度区分开来,对于同一个 height 组中,当前的 height 只能跟另一个 height 组相比求 lcp 。
一个可行的方法是,将组内不同的height都记录下来,再对于每一个当前height,我把它跟另一个height组一一求贡献。但是这个复杂度为 \( O ( n^2 ) \),显然是不行的。

最后学到的优化就是单调栈优化了,用 st[i][0]表示栈中第 i 号元素记录时候的height值,st[i][1]表示在这个height值上覆盖了st[i][1]个子串,在栈内维护height递增,实现\( O( 1 ) \) 求贡献。

#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 inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 5;

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(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 130);
        getHeight(len);
    }

    int st[maxn][2];
    void solve(int key, int limit)
    {
        ll tot = 0, top = 0, sum = 0;
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] < key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] > key)
                sum += tot;
        }
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] > key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] < key)
                sum += tot;
        }
        printf("%lld\n", sum);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int k;
    while (scanf("%d", &k) != EOF && k > 0) {
        scanf("%s", buf);
        int len = strlen(buf);
        buf[len] = '$';
        scanf("%s", buf + len + 1);
        suffix_array.input(buf);
        suffix_array.solve(len, k);
    }
    return 0;
}
后缀数组

HDU 6194 string string string

Posted on

一眼以为KMP能解,上去就是一WA……

但是我还不知道KMP的错误点……可惜看不了提交的代码了……
这道题因为我在比赛的时候被一道煞笔树形DP卡到了,因为图没清空,所以没什么时间去看,虽然最后还是有一个小时给我,但我还是没有做出来。

比赛的时候天海的解法用到了单调栈,但我看了题解还有另一个非常巧妙的做法。

题意:
给你一个字符串,问你刚好出现 k 次的子串数量。

思路:
看了大佬的题解,只给了一个方程。枚举区间为 k - 1 的 height 数组,也就是 k 的 sa,贡献为

$ max(0, lcp( i , i + k - 1 ) - max(height[ i ], height[ i + k ]) $

一开始听蒙蔽的,略加思考就察觉到了方程的正确性,对于每个区间的 LCP ,如果跟区间外的后缀一旦有重复的,那么这个公共部分就不能算及在内。因为这个部分就不是刚好出现 k 次的子串了。于是把区间 LCP 将它减去即可。

注意 k == 1 的时候需要特判。

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

    void work(int k)
    {
        height[len + 1] = 0;
        int ans = 0;
        for (int i = 1; i <= len - k + 1; i++)
            ans += max(0, query(i, k) - max(height[i], height[i + k]));
        printf("%d\n", ans);
    }

    int query(int id, int k)
    {
        return k == 1 ? len - sa[id] : RMQ(id + 1, id + k - 1);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %s", &n, buf);
        suffix_array.input(buf);
        suffix_array.initRMQ();
        suffix_array.work(n);
    }
    return 0;
}
后缀数组

POJ 3693 Maximum repetition substring

Posted on

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

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

这里放上我理解之后的思路:
首先枚举长度 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;
}
后缀数组

POJ 3261 Milk Patterns

Posted on

后缀数组之可重叠 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;
}
后缀数组

HDU 4691 Front compression

Posted on

后缀数组之最长公共前缀的不定查询。
因为查询很多,所以要结合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;
}
后缀数组

HDU 4552 怪盗基德的挑战书

Posted on

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

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

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

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

POJ 2774 Long Long Message

Posted on

后缀数组论文题,也是后缀数组的入门题——最长公共子串。
另外这题是双倍经验 HDU 1403 Longest Common Substring不过HDU的数据更水一点。

题意:
给你两个字符串,求最长公共子串。

思路:
因为是论文题,我不可能讲的比论文还详细的啦……这不是显然的吗

看了论文后基本就是套板子,因为它已经吧最关键的地方给证明了,然后有一个小地方,为什么可以直接拿 sa 数组与第一个字符串长度 key 比较呢?
那是因为,sa数组本身就是记录后缀排名第 idx 位的是哪一个后缀,而后缀和第一个字符串 key ,都是从左往右正向计数的。故可以直接拿来比较。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

#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 = 2e5 + 10;
int sa[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int t1[maxn], t2[maxn], buc[maxn];
    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)
{
    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], slen[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str), key = len;
        str[len] = '$';
        scanf("%s", str + len + 1);
        len = strlen(str);
        each(i, len+1) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int ans = 0;
        range(i, 2, len) if ((sa[i] < key) + (sa[i - 1] < key) == 1) ans = max(ans, height[i]);
        printf("%d\n", ans);
    }
    return 0;
}