如果可以通过串联同一字符串的两个副本来获得字符串，则将其称为方字符串。例如，“ 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的新子序列。
重复最后一步，直到找不到新的正方形子序列。
