题意
给定一个字符串 $S$, 求有多少种将 $S$ 的子串拆分为形如 AABB 的拆分方案
$|S|\le 30000$ ($95%$ 数据 $|S|\le 2000$)
题解
考场上遇见这题直接打95分暴力哈希跑路就完事了吧
$O(n^2)$ 暴力就直接枚举所有子串看它是不是 AA 型的, 在左右端点处分别标记一下, 然后枚举断点把两边的方案数乘起来就完事了.
考虑优化这个暴力. 我们枚举这个 AA 串中 A 的长度 $l$, 然后每隔 $l$ 取一个关键点, 那么每个 AA 串必然会覆盖两个关键点. 对于每对相邻的关键点 $a$ 和 $b$, 我们计算 $p=\operatorname{LCP}(S[a:],S[b:])$ 以及 $s=\operatorname{LCS}(S[:a-1],S[:b-1])$ . 那么只要 $p+s\ge l$ 就会有 AA 串出现. 画画图可以发现 $[a-s,a-(l-p)]$ 都可以是 AA 串的左端点. 直接在差分数组上修改左右端点就可以了. 注意只能计算同时包含这两个相邻的关键点的 AA 串, 所以应该和 $[a-l+1,a]$ 取交集. 算完之后前缀和一下按照 $O(n^2)$ 暴力里的操作算最终答案就可以了.
参考代码
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include <bits/stdc++.h>
const int MAXN=1e5+10;
typedef long long intEx;
struct SuffixArray{
char s[MAXN];
int SA[MAXN];
int rank[MAXN];
int stmin[20][MAXN];
int* height=stmin[0];
void Build();
int LCP(int,int);
};
SuffixArray pf,sf;
int n;
int lg[MAXN];
int cnt[MAXN];
char buf[MAXN];
int lcnt[MAXN];
int rcnt[MAXN];
int* x=new int[MAXN];
int* y=new int[MAXN];
int LCP(int,int);
int LCS(int,int);
int main(){
int T;
scanf("%d",&T);
for(int i=2;i<MAXN;i++)
lg[i]=lg[i>>1]+1;
while(T--){
scanf("%s",buf+1);
n=strlen(buf+1);
for(int i=1;i<=n;i++)
pf.s[i]=sf.s[n-i+1]=buf[i];
pf.Build();
sf.Build();
memset(lcnt,0,sizeof(int)*(n+1));
memset(rcnt,0,sizeof(int)*(n+1));
for(int len=1;(len<<1)<=n;len++){
for(int a=1,b;(b=a+len)<=n;a=b){
int p=LCP(a,b);
int s=LCS(a-1,b-1);
if(p+s>=len){
int l=std::max(a-len+1,a-s);
int r=std::min(a-(len-p),a);
++lcnt[l];
--lcnt[r+1];
++rcnt[l+(len<<1)-1];
--rcnt[r+(len<<1)];
}
}
}
for(int i=1;i<=n;i++){
lcnt[i]+=lcnt[i-1];
rcnt[i]+=rcnt[i-1];
}
intEx ans=0;
for(int i=1;i<n;i++)
ans+=1ll*rcnt[i]*lcnt[i+1];
printf("%lld\n",ans);
}
return 0;
}
int LCP(int a,int b){
return pf.LCP(a,b);
}
int LCS(int a,int b){
return sf.LCP(n-a+1,n-b+1);
}
int SuffixArray::LCP(int a,int b){
if(a<1||a>n||b<1||b>n)
return 0;
else if(a==b)
return n-a+1;
else{
a=rank[a];
b=rank[b];
if(a>b)
std::swap(a,b);
int p=lg[b-a];
++a;
return std::min(stmin[p][a],stmin[p][b-(1<<p)+1]);
}
}
void SuffixArray::Build(){
int m=127;
memset(x,0,sizeof(int)*(n+2));
memset(y,0,sizeof(int)*(n+2));
memset(cnt,0,sizeof(int)*(m+1));
for(int i=1;i<=n;i++)
++cnt[x[i]=s[i]];
for(int i=1;i<=m;i++)
cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)
SA[cnt[x[i]]--]=i;
for(int k=1;k<n;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++)
y[++p]=i;
for(int i=1;i<=n;i++)
if(SA[i]>k)
y[++p]=SA[i]-k;
memset(cnt,0,sizeof(int)*(m+1));
for(int i=1;i<=n;i++)
++cnt[x[i]];
for(int i=1;i<=m;i++)
cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)
SA[cnt[x[y[i]]]--]=y[i];
std::swap(x,y);
x[SA[1]]=1;
p=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])?p:++p;
if(p>=n)
break;
m=p;
}
for(int i=1;i<=n;i++)
rank[SA[i]]=i;
int k=0;
for(int i=1;i<=n;i++){
if(rank[i]==1)
continue;
if(k)
--k;
int j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])
++k;
height[rank[i]]=k;
}
for(int i=1;(1<<i)<=n;i++){
for(int j=2;j<=n;j++){
stmin[i][j]=stmin[i-1][j];
if(j+(1<<(i-1))<=n)
stmin[i][j]=std::min(stmin[i][j],stmin[i-1][j+(1<<(i-1))]);
}
}
}
|
