欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-17 14:04:30
...

题目链接


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

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

  错误一:在特判K==1的时候,应该是子串的数量,而不是文本串的长度,那么子串的数量就是Acesrc and String Theory 【HDU - 6661】【后缀数组】

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

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

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

  讲一下完整的思路,首先,K连续会让我想到我们可以枚举长度,为了算贡献,我们或许会去把所有可以达到K连续的长度给存储下来,但这样的复杂度就是逆天了的,所以这里不能这样解,我们在算的过程中,就可以把答案得到了。于是乎,我们根据论文的思路,我们想知道ii+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;
}