python - 分区中唯一子字符串的最大数量

Question

我修改了标题，以便更容易理解。

这是问题的详细版本:

我们有一个字符串s并希望将其拆分为子字符串。每个子字符串彼此不同。我们可以从一次剪切中获得的唯一子字符串的最大数量是多少。换句话说，连接形成 s 的唯一子字符串的最大数量是多少？ 。

以下是一些示例:

Example 1
s = 'aababaa'
output = 4
Explain: we can split `s` into aa|b|aba|a or aab|a|b|aa, 
         and 4 is the max number of substrings we can get from one split.

Example 2
s = 'aba'
output = 2
Explain: a|ba

Example 3
s = 'aaaaaaa'
output = 3
Explain: a|aa|aaaa

注意:s仅包含小写字符。我不知道多久s因此无法猜测最佳时间复杂度。 :(

这是一个NP难题吗？如果没有，如何有效解决？

我从一位 friend 那里听到这个问题，但无法回答。我正在尝试使用 Trie + 贪婪来解决这个问题。对于第一个示例，该方法失败。

这是我想出的 Trie 解决方案:

def triesolution(s):
    trie = {}
    p = trie
    output = 0
    for char in s:
        if char not in p:
            output += 1
            p[char] = {}
            p = trie
        else:
            p = p[char]
    return output

对于示例 1，上面的代码将返回 3，因为它试图拆分 s进入a|ab|abaa .

补充:感谢大家的想法，看起来这个问题非常接近NP问题。现在我正在尝试从这个方向去思考。假设我们有一个函数 Guess(n) 。该函数将返回True如果我们能找到n来自一次分割的唯一子字符串或 False否则。这里的一个观察结果是，如果 Guess(n) == True ，然后Guess(i) == True对于所有人i <= n 。因为我们可以将两个相邻的子串合并在一起。这种观察可以得出二元解决方案。然而，它仍然需要我们可以计算 Guess功能非常有效。遗憾的是，我仍然找不到计算 Guess(n) 的多项式方法。 .

Answer 1

这被称为碰撞感知字符串分区问题，并且在 Anne Condon、Ján Maňuch 和 Chris Thachuk 的论文 - 复杂性中通过从 3-SAT 的简化证明是 NP 完全问题碰撞感知字符串划分问题及其与基因合成寡核苷酸设计的关系(国际计算和组合学 session ，265-275，2008)。