2

可能重复：
方形子序列

我一直在尝试解决interviewstreet.com 上的“ Square Subsequences ”问题：

如果一个字符串可以通过连接相同字符串的两个副本获得，则该字符串称为方字符串。例如，“abab”、“aa”是方串，而“aaa”、“abba”则不是。

给定一个字符串，该字符串有多少个子序列是方串？

我尝试制定一个 DP 解决方案，但这个约束似乎无法规避：S will have at most 200 lowercase characters (a-z).

据我所知，找到长度列表的所有子序列n是O(2^n)，一旦n大于 30 就不再可行。

n如果是 200 ，是否真的可以系统地检查所有解决方案？我该如何处理？

4

2 回答 2

3

首先，对于每个字母，a..z您都会在以下位置获得其索引列表S：

`p[x] = {i : S[i] = x}`, where `x = 'a',..,'z'`.

然后我们开始DP：

S: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
            ^          ^    ^
            r1        l2    r2

让f(r1,l2,r2)是任意长度的方形子序列（是方形字符串的子序列）的数量L，使得

  1. SS[L-1] = r1
  2. SS[L] = l2
  3. SS[2L-1] = r2

即前半部分正好结束于r1，后半部分正好开始于l2并结束于r2。

那么算法是：

让f[r1,l2,l2] = 1if S[r1] = S[l2]，否则为 0。

for (l2 in 1..2L-1 )
    for( r1 in 0..l2-1 )
        for (r2 in l2..2L-1)
            if( f(r1, l2, r2) != 0 )
                for (x in 'a'..'z')
                    for (i,j: r1 < i < l2, r2 < j, S[i] = S[j] = x) // these i,j are found using p[x] quickly
                        f[i, l2, j] += f[r1, l2, r2]

最后，答案是f[.,.,.]数组中所有值的总和。

所以基本上，我们将Sunisgl2分成两部分，然后计算公共子序列。

我现在很难提供准确的时间复杂度估计，它肯定低于n^4并且n^4对于n = 200.

于 2012-06-28T11:54:36.490 回答
0

有许多算法（例如Z 算法）可以在线性时间内生成前缀长度数组。也就是说，对于每个位置 i，它都会告诉您从位置 i 开始可以读取的最长前缀是什么（当然，对于 i = 0，最长的前缀是 n）。

现在请注意，如果您有一个从开头开始的方形字符串，那么在这个前缀长度数组中有一个位置 k，使得最长长度 >=k。所以你可以再次计算线性时间的数量。

然后删除字符串的第一个字母并做同样的事情。总复杂度为 O(n^2)。

于 2012-06-28T09:52:53.143 回答