algorithm - 关于字符串、dp、图形或其他算法的问题

Question

问题如下。

1. 关于“不错”

   1)“ab”很好

   2) A 很好 => "a"+A+"b"很好

   3) A 和 B 很好 => A+B 很好

2. 关于“~”

   1) "ab"~"ab"

   2) A~B => "a"+A+"b"~"a"+B+"b"

   3) A~B 和 C~D => A+C~B+D 和 A+C~D+B

现在最多有 1000 个字符串 'a' 和 'b' 组成一个集合 S，找到 S 的最大子集，其中每个元素都必须是 nice 并且对 (A,B) 都不满足 A~B。输出基数。

与我之前看到的问题有一些不同:A+B+C+D~A+C+B+D~B+D+A+C 但 A+B+C+D~B+D+A+C 不成立。

我的两个困难:

1. 如何判断S1~S2是否存在
2. 如果我知道每一对的“~”，我怎样才能找到基数

更多详情:https://www.spoj.pl/problems/ABWORDS/

Answer 1

构建好词的规则意味着每个好词都以“a”开头并以“b”结尾。因此，有一个唯一的(直到排序 - 规则 3)将好词分解为好子词:找到所有“ab”，然后尝试使用规则 2 扩展它们，并使用规则 3 对它们进行排序。我们可以通过树来表示这种分解(规则 3 的重复应用 n 个分支)。

在树上下文中，“~”关系只是表示同构树，我认为(分支顺序无关紧要)。

编辑:正如所指出的，分支顺序确实很重要。

我将尝试解决原始链接中所述的问题(“nice”的两个定义不一致)。

首先，两个词 X 和 Y 之间的相似性，使用 DP。

定义f(a, b, n)为表示X[a..a+2n-1]与相似的函数Y[b..b+2n-1] 并且两个子词都很好。

f(a, b, 0) = 1.

对于 n > 0,

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n)
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1)
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k)
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k)

我认为这是 O(n^4)(呃)。

对于第二部分，如果您将单词表示为具有表示相似关系的边的图，我认为您实际上是在尝试找到最大独立集。如果是这样，祝你好运!它是 NP-hard(即没有比尝试所有更好的解决方案组合)在一般情况下，我没有看到任何使它更容易的属性:(

EDITED 使相似度的定义自动检查 niceness。这很容易。

EDITED 又是因为我的愚蠢。