Codeforces 1238D AB-string 题解
题意
一个字符串$s$如果 它的每一个字符都属于至少一个长度大于$1$的回文子串,那么称$s$是“好的”。如AABBB
,ABAA
,AAAAA
是好的。
给定一个长度为$n (1\le n\le 3\cdot10^5)$的字符串$s$,求出$s$中好的子串的个数。
题解
设一个字符串$t$由$t_1\dots t_n$组成,则$\forall 1<i<n$,$t_i$属于一个回文子串(默认长度大于$1$,以下同理)。
证明:设$i$满足$1<i<n$,
- 若$t_i=t_{i-1}$,则它属于回文串$t_{i-1}t_i$。
- 若$t_i=t_{i+1}$,则它属于回文串$t_it_{i+1}$。
- 若$t_i\neq t_{i-1},t_i\neq t_{i+1}$,那么$t_{i-1}=t_{i+1}$,则它属于回文串$t_{i-1}t_it_{i+1}$。
那么,只有当$i=1$或$i=n$时,$t_i$才有可能不属于一个回文子串。
下面考虑$t_1$不属于一个回文子串的情况。
- $t_2\neq t_1$,否则$t_1$属于回文串$t_1t_2$。
- $\forall i>2$,$t_i\neq t_{i-1}$,否则$t_1$属于回文串$t_1\dots t_i$
$t_n$同理。
所以,$t$只有形如以下四种字符串时,$t$不是好的。
AB...B
BA...A
A...AB
B...BA
给定$s$,求$s$中好的子串的个数,那么就可以转化为 所有子串-不是好的子串,即$\frac{n\times(n-1)}{2}-cnt$,$cnt$为不是好的子串。
显然,$cnt$可以$O(n)$求出。
程序
1 | // #pragma GCC optimize(2) |
Tip: 这个程序看似是$O(n^2)$的,实际上是$O(n)$的。这里不再赘述。