Codeforces 1238D – AB-string

题目链接:Codeforces 1238D

反向考虑,要求好子串的数量,就用总字串的数量$n \choose 2$里减去坏子串的数量。$n \choose 2$的原因是长度为1的可以不用考虑,它一定是不满足条件的,所以总量是长度大于等于2的所有子串的数量,要减去的是长度大于等于2的所有坏子串的数量。

考虑什么样的串是坏的,对于一个子串$t[1\cdots k]$,只要存在一个$t[i]$不包含于任何一个长度大于二的回文中,那么$t[1\cdots k]$就是坏的。而实际上,$t[i]=t[i-1]$或$t[i]=t[i+1]$的时候,显然是存在的,因为至少有一个长度为2的回文,如果$t[i] \neq t[i-1]$并且$t[i] \neq t[i+1]$,那么可以形成长度为3的回文。所以如果存在这样一个$t[i]$使得$t[1\cdots k]$是坏的,那么要么$i=1$,要么$i=k$。

如果我们从$t[2]$往后能找到一个(最前面一个)$t[i]=t[1]$,那么说明$t[1]$一定包含在回文串里,对于$t[k]$类似。所以坏的串具有这样的形式:

  • ABB…B
  • BAA…A
  • A…AAB
  • B…BBA

所以$O(n)$统计这些串的个数就可以了。

 

说点什么

avatar
50
  Subscribe  
提醒