广场子序列 [英] Square Subsequence

问题描述

一个字符串被称为正方形字符串，如果它能够通过链接相同的字串的两个副本而获得。例如，ABAB，AA是方形字符串，而AAA，阿巴不是。给定一个字符串，有多少串子序列是方形的字符串？可以通过删除零个或更多字符从它，并保持剩余characters.The子序列的相对顺序不必是唯一的获得的字符串的一个子序列。

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how many subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.The subsequence need not be unique.

如字符串'AAA'将有3万个子

eg string 'aaa' will have 3 square subsequences

推荐答案

观察1：一个正方形字符串的长度总是偶数

Observation 1: The length of a square string is always even.

观察2：长度为2n（N> 1）中的每平方亚序列是两个较短的子序列的组合：长度2（N-1）和中的一个长度2

Observation 2: Every square subsequence of length 2n (n>1) is a combination of two shorter subsequences: one of length 2(n-1) and one of length 2.

首先，查找长度的两个序列，即发生两次或更多次的字符串中的字符。我们称这些的对的。为长度2（1对）的每个子序列，记住该序列中的第一个和最后一个字符的位置。

First, find the subsequences of length two, i.e. the characters that occur twice or more in the string. We'll call these pairs. For each subsequence of length 2 (1 pair), remember the position of the first and last character in the sequence.

现在，假设我们有长度为2（N-1）的所有子序列，我们知道用​​于第一和第二部分的开始和结束字符串中的每个在哪里。我们可以通过观察发现2长度为2n的序列：

Now, suppose we have all subsequences of length 2(n-1), and we know for each where in the string the first and second part begins and ends. We can find sequences of length 2n by using observation 2:

穿过长度为2（N-1）的所有的子序列，并查找所有对其中在该对中的第一项位于第一部分的最后位置和第二部分的第一位置，和第二项之间第二部分的最后位置之后所在。这样一对被发现每一次，长度为2（N-2）的当前子序列结合入长度为2n的一个新的序列。

Go through all the subsequences of length 2(n-1), and find all pairs where the first item in the pair lies between the last position of the first part and the first position of the second part, and the second item lies after the last position of the second part. Every time such a pair is found, combine it with the current subsequence of length 2(n-2) into a new subsequence of length 2n.

重复最后一步，直到不再有新的多子序列被发现。

Repeat the last step until no more new square subsequences are found.

这篇关于广场子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！