Acesrc and String Theory 【HDU - 6661】【后缀数组】

题目链接

---

  题目问的是有多少个K连续重复子串，即连续出现K次的重复子串。

  思路：肯定是往后缀数组上想，但是中间出了点差错。

  错误一：在特判K==1的时候，应该是子串的数量，而不是文本串的长度，那么子串的数量就是。

  错误二：在我们枚举长度L的时候，算他们同时包含i和i + L的且连续出现次数大于等于K的时候的贡献，我算的贡献是前面往后有几种排列组合。但这是错误的，可以用整个的长度减去K*L再+1即可，因为我们可以在这段长度中任意滑动组成全长。

  错误三：我们的跳转，应该是跳转到最右边匹配到的位置的后面的位置，当然，为了保证复杂度，我们可以利用每次“+L”来看它是否会跳过去来保证其复杂度。

  总结了以上错误，然后才坎坎过了这题。

  讲一下完整的思路，首先，K连续会让我想到我们可以枚举长度，为了算贡献，我们或许会去把所有可以达到K连续的长度给存储下来，但这样的复杂度就是逆天了的，所以这里不能这样解，我们在算的过程中，就可以把答案得到了。于是乎，我们根据论文的思路，我们想知道i和i+L这两个点向左和向右的最长匹配（求LCP），也就是求height了。于是，我们不难算出最长连续匹配了，也就是包好i和i+L这两个点的最长（以L为循环节长度的）最长匹配长度了，然后我们可以将K*L左右滑动来记答案，所以这里的答案是总的长度减去K*L再加上1即可得到，然后统计全部答案即可。记得开long long。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 3e5 + 7;
struct SA
{
    int n, m;
    int s[maxN];
    int y[maxN], x[maxN], c[maxN], sa[maxN], rk[maxN], height[maxN];
    inline void get_SA()
    {
        for(int i=1; i<=m; i++) c[i] = 0;   //桶的初始化
        for(int i=1; i<=n; i++) ++c[x[i] = s[i]];
        for(int i=2; i<=m; i++) c[i] += c[i - 1];   //利用差分前缀和的思想知道每个关键字最多是在第几名
        for(int i=n; i>=1; i--) sa[c[x[i]]--] = i;
        for(int k=1; k<=n; k<<=1)
        {
            int num = 0;
            for(int i=n - k + 1; i<=n; i++) y[++num] = i;
            for(int i=1; i<=n; i++) if(sa[i] > k) y[++num] = sa[i] - k; //是否可以作为第二关键字
            for(int i=1; i<=m; i++) c[i] = 0;
            for(int i=1; i<=n; i++) c[x[i]]++;  //因为上一次循环已经求出这次的第一关键字了
            for(int i=2; i<=m; i++) c[i] += c[i - 1];
            for(int i=n; i>=1; i--) //在同一第一关键字下，按第二关键字来排
            {
                sa[c[x[y[i]]]--] = y[i];
                y[i] = 0;
            }
            swap(x, y);
            x[sa[1]] = 1; num = 1;
            for(int i=2; i<=n; i++)
            {
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
            }
            if(num == n) break;
            m = num;
        }
    }
    inline void get_height()
    {
        int k = 0;
        for(int i=1; i<=n; i++) rk[sa[i]] = i;
        for(int i=1; i<=n; i++)
        {
            if(rk[i] == 1) continue;    //第一名的height为0
            if(k) k--;  //height[i] >= height[i - 1] - 1
            int j = sa[rk[i] - 1];
            while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k++;
            height[rk[i]] = k;
        }
    }
    inline void clear()
    {
        n = 0; m = 200;
    }
} sa[2];
int LOG[maxN];
struct RMQ_struct
{
    int N;
    int dp_min[maxN][20];
    void RMQ(int id)
    {
        for(int i=1; i<=N; i++) dp_min[i][0] = sa[id].height[i];
        for(int j=1; (1 << j) <= N; j++)
        {
            for(int i=1; i + (1 << j) - 1 <= N; i++)
            {
                dp_min[i][j]=min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int query(int l, int r)
    {
        int i = LOG[r - l + 1];
        return min(dp_min[l][i], dp_min[r - (1 << i) + 1][i]);
    }
} rbt[2];
int N, K;
ll ans;
char s[maxN];
inline void sure_lenth()
{
    for(int L=1, k_len, l, r, k2_len, l2, r2, all_len; L <= N / K; L++) //枚举长度
    {
        int i = 1;
        while(i + L <= N)
        {
            if(s[i] ^ s[i + L]) { i += L; continue; }
            l = sa[0].rk[i]; r = sa[0].rk[i + L];
            if(l > r) swap(l, r);
            l2 = sa[1].rk[N - (i + L) + 1]; r2 = sa[1].rk[N - (i) + 1];
            if(l2 > r2) swap(l2, r2);
            k_len = rbt[0].query(l + 1, r);
            k2_len = rbt[1].query(l2 + 1, r2);
            all_len = k_len + k2_len + L - 1;
            if(i + k_len - 1 + 1 < i + L - k2_len + 1) { i += L; continue; }
            if(all_len >= K * L)
            {
                ans += all_len - K * L + 1;
            }
            int nex_pos = i + L + k_len;
            while(i < nex_pos) i += L;
        }
    }
}
int main()
{
    LOG[0] = 0; LOG[1] = 0;
    for(int i=1; (i << 1) < maxN; i <<= 1) LOG[i << 1] = LOG[i] + 1;
    for(int i=3; i < maxN; i++) LOG[i] = max(LOG[i], LOG[i - 1]);
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &K);
        scanf("%s", s + 1);
        N = (int)strlen(s + 1);
        if(K == 1) { printf("%lld\n", 1LL * N * (N + 1) / 2); continue; }
        sa[0].clear(); sa[1].clear();
        for(int i=1; i<=N; i++) sa[0].s[++sa[0].n] = s[i];
        for(int i=N; i>=1; i--) sa[1].s[++sa[1].n] = s[i];
        sa[0].s[++sa[0].n] = 'a' + 26;
        sa[1].s[++sa[1].n] = 'a' + 26;
        sa[0].get_SA();
        sa[0].get_height();
        sa[1].get_SA();
        sa[1].get_height();
        rbt[0].N = N;
        rbt[0].RMQ(0);
        rbt[1].N = N;
        rbt[1].RMQ(1);
        ans = 0;
        sure_lenth();
        printf("%lld\n", ans);
    }
    return 0;
}