「HDU-6661」Acesrc and String Theory (后缀数组)

发表于 | 分类于 ，

「HDU-6661」Acesrc and String Theory
给定一个串，问由k个循环节组成的子串数量

题解

考虑找到一个由循环节构成的联通块。枚举循环节长度$i∈(1,n/2)$，找到区间$[L,R]$为某个循环节长度为$i$的极大循环节（向右能够扩展的长度小于$i$），求得$extR=lcp(s(L),s(R+1))$为该串可以向右扩展的最大长度，并翻转原串求出向左扩展的最大长度$extL=lcp(revs(n+1-R), revs(n+1-L+1))$，那么求出的块为$[l,r]$为$[L-extL,R+extR]$。当前块对答案的贡献为“长度为$r-l+1$的串中长度为$k×i$的子串个数”，即$(r-l+1)-k×i+1$。

当$k=1​$时需要特判。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;

struct SA
{
    char s[maxn];
    int sa[maxn], t[maxn], t2[maxn], c[maxn], n;

    void build_sa(int n, int m)
    {
        int *x = t, *y = t2;
        for(int i = 0; i < m; i++) c[i] = 0;
        for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
        for(int i = 1; i < m; i++) c[i] += c[i - 1];
        for(int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
        for(int k = 1; k <= n; k <<= 1)
        {
            int p = 0;
            for(int i = n - k; i < n; i++) y[p++] = i;
            for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
            for(int i = 0; i < m; i++) c[i] = 0;
            for(int i = 0; i < n; i++) c[x[y[i]]]++;
            for(int i = 0; i < m; i++) c[i] += c[i - 1];
            for(int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1; x[sa[0]] = 0;
            for(int i = 1; i < n; i++)
                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;
        }
    }

    int rk[maxn], height[maxn];

    void getHeight()
    {
        for(int i = 1; i <= n; i++) rk[sa[i]] = i;
        for(int i = 0, k = 0; i < n; i++)
        {
            if(k) k--;
            int j = sa[rk[i] - 1];
            while(s[i + k] == s[j + k]) k++;
            height[rk[i]] = k;
        }
        for(int i = n; i > 0; i --) rk[i] = rk[i - 1];
    }

    int dp[maxn][21];

    void RMQ()
    {
        for(int i = 1; i <= n; i ++) dp[i][0] = height[i];
        for(int j = 1; (1 << j) < maxn; j ++)
            for(int i = 1; i + (1 << j) - 1 <= n; i ++)
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }

    int query(int l, int r)
    {
        int k = 0;
        while((1 << (k + 1)) <= r - l + 1) k ++;
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }

    int lcp(int x, int y)
    {
        x = rk[x], y = rk[y];
        if(x > y) swap(x, y);
        return query(x + 1, y);
    }
}A, B;

int n, k;

int work(int l, int r, int p)
{
    int exR = A.lcp(l, r + 1), exL = B.lcp(n + 1 - r, n + 1 - l + 1);
    l -= exL, r += exR;
    return max(0, r - l + 1 - p * k + 1);
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%d%s", &k, A.s);
        n = strlen(A.s);
        if(k == 1)
        {
            printf("%lld\n", 1ll * n * (n + 1) / 2);
            continue;
        }
        reverse_copy(A.s, A.s + n, B.s); A.n = B.n = n;
        A.build_sa(n + 1, 130), B.build_sa(n + 1, 130);
        A.getHeight(), B.getHeight();
        A.RMQ(), B.RMQ();
        ll ans = 0;
        for(int i = 1; i <= n / 2; i ++)
        {
            int last = 1;
            for(int j = i + 1; j <= n; j += i)
            {
                if(A.lcp(last, j) >= i) continue;
                ans += work(last, j - 1, i);
                if(j + i - 1 <= n) last = j;
                else last = 0;
            }
            if(last) ans += work(last, n, i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}