任务量统计
工作日五道题
(
5
/
5
)
(5/5)
(5/5)
链接
https://cn.vjudge.net/problem/UVA-10829
题解
这题有点神啊 对于形如
A
B
A
ABA
ABA的串，我枚举
A
A
A的长度
u
u
u，然后把整个字符串按照
u
u
u分块，然后谜之乱搞… 我觉得按照
u
u
u分块的意义在于：我想要统计长度恰好为
u
u
u的满足条件的子串
A
A
A的个数，分块之后就带来一个便利，子串
A
A
A的左端点和右端点必然在相邻的两个块中（假设在同一个块中，那么区间长度小于
u
u
u；假设在不同的块中，那么区间长度大于
u
u
u） 那么分块之后我就有一个很显然的思路，在每个块中枚举左端点
l
l
l，再根据我枚举的
u
u
u确定串
A
A
A的位置，然后每个字符下标加上
u
+
g
u+g
u+g就得到了后面待匹配串的位置，进行暴力匹配从而统计答案 考虑怎么优化：既然每次比较的两个字符的坐标之差为
u
+
g
u+g
u+g，那么我是否可以先预处理一下对应位置的字符是不是相等？ 如果相等我就放一个
1
1
1，不相等我就放一个
0
0
0，那么其实是统计左端点在我所枚举的块内，长度为
u
u
u的连续
1
1
1区间的个数。 假如我把每个长度为
u
u
u的块的范围设为左闭右开，可以发现所有的区间都包含了块的最后一个点(编号为
i
∗
u
−
1
i*u-1
i∗u−1），既然要统计包含这个点的全
1
1
1区间，我可以从这个点往前统计连续
1
1
1的个数
l
1
l1
l1，往后统计连续
1
1
1的个数
l
2
l2
l2，那么这个块对答案的贡献就是
m
a
x
(
0
,
l
1
+
l
2
−
l
+
1
)
max(0,l1+l2-l+1)
max(0,l1+l2−l+1) 后缀数组加速一下，每次查询
O
(
1
)
O(1)
O(1)，总复杂度是
O
(
n
ln
(
n
)
)
O(n\ln(n))
O(nln(n))
总结
遇到一个字符串题，不一定先往算法上套。也许可以先想暴力怎么做，然后再用数据结构或者算法来优化。当然也不是绝对的，到底是先想数据结构/算法，还是先想怎么暴力，这二者还是要靠直觉和经验进行搭配。
一种口胡做法
这题可以等价于求
∣
s
a
x
−
s
a
y
∣
≤
l
c
p
(
x
,
y
)
+
g
|sa_x-sa_y|\leq lcp(x,y)+g
∣sax−say∣≤lcp(x,y)+g的点对
(
x
,
y
)
(x,y)
(x,y)的个数
l
c
p
lcp
lcp实际上就是一堆
h
e
i
g
h
t
height
height取
m
i
n
min
min，我先预处理出来每个
h
e
i
g
h
t
height
height作为
m
i
n
min
min的有效区间，然后这个
h
e
i
g
h
t
height
height就可以把有效区间分成两半，假设这个
h
e
i
g
h
t
height
height是
t
t
t，那么就是找
∣
s
a
x
−
s
a
y
∣
≤
t
+
g
|sa_x-sa_y| \leq t+g
∣sax−say∣≤t+g的
(
x
,
y
)
(x,y)
(x,y)的个数。这两段区间里肯定有一个较小的段，我先在这个区间枚举
i
i
i，然后用主席树到对应的另一半区间里去找符合条件的解，复杂度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n) （可能会写，也可能就这样扔着qwq）
代码
#include <bits/stdc++.h>
#define maxn 50010
#define maxk 17
#define cl(x) memset(x,0,sizeof(x))
using namespace std
;
typedef long long ll
;
struct SuffixArray
{
int sa
[maxn
], rank
[maxn
], ws
[maxn
], wv
[maxn
], wa
[maxn
], wb
[maxn
], height
[maxn
], st
[maxk
+2][maxn
], N
;
bool cmp(int *r
, int a
, int b
, int l
){return r
[a
]==r
[b
] and r
[a
+l
]==r
[b
+l
];}
void clear()
{
cl(sa
), cl(rank
), cl(ws
), cl(wv
), cl(wa
), cl(wb
), cl(height
), cl(st
);
}
void build(int *r
, int n
, int m
)
{
N
=n
;
n
++;
int i
, j
, k
=0, p
, *x
=wa
, *y
=wb
, *t
;
for(i
=0;i
<m
;i
++)ws
[i
]=0;
for(i
=0;i
<n
;i
++)ws
[x
[i
]=r
[i
]]++;
for(i
=1;i
<m
;i
++)ws
[i
]+=ws
[i
-1];
for(i
=n
-1;i
>=0;i
--)sa
[--ws
[x
[i
]]]=i
;
for(p
=j
=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
<n
;i
++)wv
[i
]=x
[y
[i
]];
for(i
=0;i
<m
;i
++)ws
[i
]=0;
for(i
=0;i
<n
;i
++)ws
[wv
[i
]]++;
for(i
=1;i
<m
;i
++)ws
[i
]+=ws
[i
-1];
for(i
=n
-1;i
>=0;i
--)sa
[--ws
[wv
[i
]]]=y
[i
];
for(t
=x
,x
=y
,y
=t
,p
=1,i
=1,x
[sa
[0]]=0;i
<n
;i
++)
x
[sa
[i
]]=cmp(y
,sa
[i
-1],sa
[i
],j
)?p
-1:p
++;
}
for(i
=0;i
<n
;i
++)rank
[sa
[i
]]=i
;
for(i
=0;i
<n
-1;height
[rank
[i
++]]=k
)
for(k
?k
--:0,j
=sa
[rank
[i
]-1];r
[i
+k
]==r
[j
+k
];k
++);
}
void build_st()
{
int i
, k
;
for(i
=1;i
<=N
;i
++)st
[0][i
]=height
[i
];
for(k
=1;k
<=maxk
;k
++)
for(i
=1;i
+(1<<k
)-1<=N
;i
++)
st
[k
][i
]=min(st
[k
-1][i
],st
[k
-1][i
+(1<<k
-1)]);
}
int lcp(int x
, int y
)
{
int l
=rank
[x
], r
=rank
[y
];
if(l
>r
)swap(l
,r
);
if(l
==r
)return N
-sa
[l
];
int t
=log2(r
-l
);
return min(st
[t
][l
+1],st
[t
][r
-(1<<t
)+1]);
}
}SA1
, SA2
;
int read(int x
=0)
{
int c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-48;
return f
*x
;
}
char s
[maxn
];
int r
[maxn
];
int main()
{
int T
=read(), len
, g
, i
, L
, R
, mid
, kase(0), u
;
ll ans
;
while(T
--)
{
g
=read();
scanf("%s",s
);
len
=strlen(s
);
for(i
=0;i
<len
;i
++)r
[i
]=s
[i
]-'a'+1;
r
[len
]=0;
SA1
.clear();
SA1
.build(r
,len
,30);
SA1
.build_st();
reverse(r
,r
+len
);
r
[len
]=0;
SA2
.clear();
SA2
.build(r
,len
,30);
SA2
.build_st();
ans
=0ll;
for(u
=1;u
<=len
;u
++)
{
for(i
=u
-1;i
<len
;i
+=u
)
{
int l1
, l2
;
if(i
+1+u
+g
>=len
)l2
=0;
else l2
=min(u
-1,SA1
.lcp(i
+1,i
+1+g
+u
));
if(i
+u
+g
>=len
)break;
else l1
=min(u
,SA2
.lcp(len
-(i
+u
+g
)-1,len
-i
-1));
ans
+=max(0,l1
+l2
-u
+1);
}
}
printf("Case %d: %lld\n",++kase
,ans
);
}
return 0;
}
