构造好词的规则意味着每个好词都以“a”开头并以“b”结尾。因此,有一个独特的(直到排序 - 规则 3)将好词分解为好子词:找到所有“ab”,然后尝试使用规则 2 扩展它们,并使用规则 3 对它们进行排序。我们可以通过一棵树来表达这种分解(n 个分支,用于重复应用规则 3)。
在树的上下文中,我认为“~”关系只是表示同构树(分支顺序无关紧要)。
编辑:正如所指出的,分支顺序确实很重要。
我将尝试解决原始链接中所述的问题(“nice”的 2 个定义不一致)。
首先,两个词 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 难的(即没有比尝试所有组合更好的解决方案),而且我没有看到任何属性可以使它更容易:(
编辑使相似性的定义自动检查niceness。这很容易。
由于我的愚蠢,再次编辑。