string - 方形子序列

Question

如果一个字符串可以通过连接同一字符串的两个副本而获得，则该字符串称为方形字符串。例如，“abab”、“aa”是方形字符串，而“aaa”、“abba”则不是。给定一个字符串，该字符串有多少个子序列是方形字符串？从字符串中删除零个或多个字符，并保持剩余字符的相对顺序，可以获得字符串的子序列。子序列不必是唯一的。

例如字符串 'aaa' 将有 3 个正方形子序列

Answer 1

观察 1:方形字符串的长度总是偶数。

观察 2:每个长度为 2n (n>1) 的正方形子序列都是两个较短子序列的组合:一个长度为 2(n-1)，另一个长度为 2。

首先，找到长度为2的子序列，即在字符串中出现两次或更多次的字符。我们称这些对。对于每个长度为 2 的子序列(1 对)，记住序列中第一个和最后一个字符的位置。

现在，假设我们有长度为 2(n-1) 的所有子序列，并且我们知道字符串中第一部分和第二部分开始和结束的每个位置。我们可以使用观察 2 找到长度为 2n 的序列:

遍历所有长度为 2(n-1) 的子序列，并找到所有对中第一项位于第一部分的最后位置和第二部分的第一个位置之间的所有对，以及第二项位于第二部分的最后位置之后。每次找到这样的一对，将其与当前长度为 2(n-2) 的子序列组合成一个新的长度为 2n 的子序列。

重复最后一步，直到找不到新的正方形子序列。