Acesrc and String Theory[hdu6661]

发表于 分类于

题目链接

HDU 6661

题意

给一个由小写字母组成的字符串，和一个 $k$，求有多少个非空子串满足这个子串是由某个字符串重复 $k$ 次组成的。

$|S|\leq 3\times 10^5,\sum |S|\leq 10^6,k\leq 20$

题解

这题是 $\mbox{NOI2016}$ 优秀的拆分的强化版。

一个合法的子串一定是形如 $AA\cdots A$ ($k$个$A$) ，那么我们试着枚举 $A$ 的长度 $i$。

类似“优秀的拆分”的做法，我们每隔 $i$ 个位置放一个隔板。如当 $i=3$ 时的一个例子：

0

可以发现，一个合法的子串一定刚好横跨了 $k$ 个隔板，我们试着枚举这些隔板是哪几个，设为 $b_i$。

设 $m_1=\min(i,LCP(Suf_{b_k},Suf_{b_{k+1}})),m_2=\min(i,LCS(Pre_{b_k},Pre_{b_{k+1}}))$

其中$\mbox{LCP}=\mbox{Longest Common Prefix},\mbox{LCS}=\mbox{Longest Common Suffix}$

若 $m_1+m_2>i$，则对答案有 $m_1+m_2-i$ 的贡献。

还是上面的例子，当 $k=2$ ，取前两个隔板的情况为：

1

求最长公共前后缀用 $\mbox{SA}$ + $\mbox{ST}$表就可以做到 $O(n\log n)-O(1)$。

总的时间复杂度 $O(n\log n+k\sum_{i=1}^{\frac{n}{k}}\frac{n}{i})=O(kn\log n)$

代码

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
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define N 1000010
#define ll long long
#define inf 0x3f3f3f3f
inline int read()
{
    int x=0; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
int Log[N];
struct SA{
    int n,base[N],wx[N],wy[N],sa[N],rank[N],height[N];
    char s[N];
    void getsa(char *s,int n,int m)
    {
        int *x = wx,*y = wy;
        for(int i=0;i<m;i++) base[i] = 0;
        for(int i=0;i<n;i++) base[x[i] = s[i]]++;
        for(int i=1;i<m;i++) base[i] += base[i-1];
        for(int i=n-1;i>=0;i--) sa[--base[x[i]]] = i;
        for(int i,j=1,p=1;p<n;j<<=1,m=p)
        {
            for(p=0,i=n-j;i<n;i++) y[p++] = i;
            for(i=0;i<n;i++) if(sa[i]>=j) y[p++] = sa[i]-j;
            for(i=0;i<m;i++) base[i] = 0;
            for(i=0;i<n;i++) base[x[y[i]]]++;
            for(i=1;i<m;i++) base[i] += base[i-1];
            for(i=n-1;i>=0;i--) sa[--base[x[y[i]]]] = y[i];
            swap(x,y);
            for(i=1,p=1,x[sa[0]] = 0;i<n;i++)
                x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j])?p-1:p++;  
        }
    }
    void calc_height(char *s,int n)
    {
        for(int i=1;i<=n;i++) rank[sa[i]] = i;
        for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
            for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
    }
    int f[N][22];
    void get_st()
    {
        memset(f,0,sizeof(f));
        for(int i=2;i<=n;i++) f[i][0]=height[i];
        for(int j=1,k=1;j<=19;++j,k<<=1)
            for(int i=2;i+k*2-1<=n;++i)
                f[i][j]=min(f[i][j-1],f[i+k][j-1]);
    }
    inline int lcp(int x,int y)
    {
        x=rank[x-1]; y=rank[y-1];
        if(x>y) swap(x,y); x++;
        int k=Log[y-x+1];
        return min(f[x][k],f[y-(1<<k)+1][k]);
    }
    void init()
    {
        memset(sa,0,sizeof(sa));
        memset(height,0,sizeof(height));
        memset(rank,0,sizeof(rank));
    }
    void work()
    {
        init();
        getsa(s,n+1,28);
        calc_height(s,n);
        get_st();
    }
};
SA A,B;

int bl[N],n,k;
ll sum[N];
inline ll solve()
{
    ll ans=0;
    if(k==1) return 1ll*n*(n+1)/2;
    memset(sum,0,sizeof(sum));
    for(int i=1,m1,m2;i<=n;i++)
    {
        for(bl[1]=i;bl[1]+(i*(k-1))<=n;bl[1]+=i)
        {
            for(int j=2;j<=k;j++) bl[j]=bl[j-1]+i;
            m1=m2=i;
            for(int j=1;j<k&&m1+m2>i;j++) m1=min(m1,A.lcp(bl[j],bl[j+1])),m2=min(m2,B.lcp(n-bl[j]+1,n-bl[j+1]+1));
            if(m1+m2>i) ans+=m1+m2-i;
        }
    }
    return ans;
}
char s[N];
int main()
{
    for(int i=2;i<N;i++) Log[i]=Log[i>>1]+1;
    for(int _=read();_--;)
    {
        k=read(); scanf("%s",s); n=strlen(s);
        for(int i=0;i<n;i++) A.s[i]=s[i]-'a'+1;
        for(int i=0;i<n;i++) B.s[i]=s[n-i-1]-'a'+1;
        A.n=B.n=n,A.s[n]=B.s[n]=0,A.work(),B.work();
        printf("%lld\n",solve());
    }
    return 0;
}