Avi*_*ash 13 string algorithm dynamic-programming
如果可以通过连接相同字符串的两个副本来获取字符串,则将其称为方形字符串.例如,"abab","aa"是方形字符串,而"aaa","abba"不是.给定一个字符串,该字符串的子序列有多少是方形字符串？可以通过从中删除零个或多个字符并保持剩余字符的相对顺序来获得字符串的子序列.子序列不必是唯一的.
例如,字符串'aaa'将具有3个方形子序列
观察1:方形字符串的长度始终是均匀的.
观察2:长度为2n(n> 1)的每个方形子序列是两个较短子序列的组合:一个长度为2(n-1),另一个长度为2.
首先,找到长度为2的子序列,即字符串中出现两次或更多次的字符.我们称这些对.对于长度为2(1对)的每个子序列,请记住序列中第一个和最后一个字符的位置.
现在,假设我们拥有长度为2(n-1)的所有子序列,并且我们知道每个字符串中第一和第二部分的开始和结束位置.我们可以通过观察2找到长度为2n的序列:
遍历长度为2(n-1)的所有子序列,找到该对中第一项位于第一部分的最后位置和第二部分的第一个位置之间的所有对,第二项位于第二部分的最后位置.每次找到这样的一对时,将它与当前长度为2(n-2)的子序列组合成一个长度为2n的新子序列.
重复最后一步,直到找不到新的方形子序列.