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

Question

我修改了标题，以使其更易于理解。

这是问题的详细版本：

我们有一个字符串s ，想要将其拆分为子字符串。每个子字符串彼此不同。一次切割最多可以拥有的唯一子字符串的数量是多少。换句话说，串联形成form的唯一子字符串的最大数量是多少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难题吗？如果没有，如何有效解决？

我从我的一个朋友那里听到了这个问题，无法解决。我正在尝试使用Trie +贪婪解决此问题。对于第一个示例，该方法失败。

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

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

例如1，上面的代码将尝试拆分s为，因此返回3 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ánMa？uch和Chris Thachuk在一篇论文中通过将3-SAT减少为NP-完全证明了-冲突感知字符串分区问题的复杂性及其与用于基因合成的寡核苷酸设计的关系（国际计算和组合学会议，265-275，2008）。

Answer 2

（非常感谢Gilad Barkan（???? ????）使我意识到了这一讨论。）

让我从纯理论的角度分享我对这个问题的想法（请注意，我也使用“因数”而不是“子词”）。

我认为这里考虑的一个或多个问题的正式定义如下：

给定单词w，找到单词u_1，u_2，...，u_k使得

• u_i！= u_j对于每个i，j的1 <= i <j <= k
• u_1 u_2 ... u_k = w

最大化变体（我们想要很多u_i）：最大化k

最小化变体（我们想要短的u_i）：最小化max {| u_i | ：1 <= i <= k}

这些问题通过另外给定边界B而成为决策问题，根据我们在说“多因素”变量还是“短因素”变量，边界B是k的下界（我们至少希望B因子）或max {| u_i |的上限 ：1 <= i <= k}（我们希望长度的因子至多为B）。为了谈论NP硬度，我们需要谈论决策问题。

让我们将术语SF用于“短因子”变量，将MF用于“许多因子”变量。特别是，这是非常关键的一点，问题的定义方式是使我们在某个字母上得到一个不受任何限制的单词。问题的版本是我们先验地知道，我们只能获得输入单词，例如字母{a，b，c，d}是另一个问题！NP-硬度并没有自动地从“无限制”结转到“固定字母”变体（后者可能是更简单）。

SF和MF都是NP完全问题。这已分别在[1，1b]和[2]中显示（正如Gilad已经指出的那样）。如果我在讨论开始时正确地理解了（也许也是）非正式问题的定义，那么讨论的问题就是MF问题。最初并没有提到单词仅限于某些固定的字母，后来又说我们可以假定仅使用小写字母。如果这意味着我们只考虑固定字母{a，b，c，...，z}上的单词，那么就NP硬度而言，这实际上将发生很大变化。

仔细研究发现，SF和MF在复杂性方面存在一些差异：

1. 论文[1，1b]表明，如果我们将字母固定为二进制字母，则SF仍为NP完整的（更准确地说：将单词w覆盖字母a和b以及边界B，我们可以将其分解为不同的长度因子）最多B？）。
2. 论文[1，1b]表明，如果我们将边界B固定为2，则SF仍然是NP完全的（更确切地说：得到一个单词w，我们能否将其分解为最多2个不同的长度因子？）。
3. 论文[3]表明，如果字母和边界B都是固定的，则SF可以在多项式时间内求解。
4. 论文[2]表明MF是NP完全的，但前提是字母不受先验的限制或固定！特别是，如果我们仅考虑某个固定字母上的输入单词（在实际情况下通常如此），那么它是否回答了NP完全问题并不能回答问题。
5. 论文[3]表明，如果输入边界B再次由某个常数作为上界，则MF可以在多项式时间内求解，即问题输入是一个单词和{1，2，...，K}的边界B ，其中K是某个固定常数。

关于这些结果的一些注释：Wrt（1）和（2），直观上很清楚，如果字母是二进制的，那么，为了使问题SF变得困难，边界B也不能固定。相反，固定B = 2意味着字母大小必须变得相当大才能产生困难的实例。结果，（3）显得微不足道（实际上，[3]说得更多：我们不仅可以在运行时求解多项式，而且可以将| w | ^ 2倍仅取决于字母大小的因数）求解并绑定到B）。（5）也不难：如果我们的单词比B长，那么我们可以通过简单地切成不同长度的因子来获得期望的分解。如果不是，那么我们可以蛮力所有可能性，这仅在B中呈指数关系，在这种情况下，B被假定为常数。

因此，我们得到的结果如下：SF似乎更困难，因为即使对于固定的字母或固定的边界B，我们也有硬度。另​​一方面，如果边界固定，则问题MF可以被多项式求解。在这方面，它比SF容易），而对应的问题是字母大小未定。因此，即使事实证明固定字母的MF也是NP完整的，MF的复杂度也比SF略小。但是，如果可以证明MF可以在固定时间内解决固定字母的问题，那么MF比SF容易得多……因为一种很难解决的情况是人为的（无界字母！） 。

我确实花了点力气试图解决带有有界字母的MF的情况，但此后我无法解决并停止研究。我不相信其他研究人员已经尽力解决了这个问题（因此，这不是这些非常艰巨的公开问题之一，许多人已经尝试并失败了；我认为这是可行的）。我的猜测是，对于固定字母来说这也是NP难的，但是减少的过程可能是如此复杂，以至于您会得到类似“对于35或更大的字母来说MF很难”之类的东西，这也不是太好了。

关于其他文献，我知道论文[4]，该论文考虑了将单词w分解为都是回文的不同因子u_1，u_2，...，u_k的问题，这些因子也是NP完全的。

我快速浏览了Gilad指出的论文[5]。不过，似乎要考虑其他设置。在本文中，作者对一个给定单词中可以包含多少个不同的子序列或子单词的组合问题感兴趣，但是它们可以重叠。例如，aaabaab包含20个不同的子词a，b，aa，ab，ba，bb，aaa，aab，aba，baa，baaa，aaab，aaba，abaa，baab，aaaba，aabaa，abaab，aabaab，aaabaa，aaabaab（也许我误算了，但您知道了）。其中一些仅出现一次，例如baa，其中一些仅发生一次，例如aa。无论如何，问题不在于我们如何以某种方式拆分单词以获取许多不同的因素，因为这意味着每个单独的符号都恰好构成一个因素。

关于解决此类问题的实际解决方案（请记住，我是一名理论家，因此请慎重考虑）：

• 据我所知，如果我们只考虑固定字母上的输入单词，那么就没有理论上的下界（例如NP硬度）会排除在多项式时间内求解MF的可能性。但是，有一个警告：如果您采用了多重时间算法，则该算法应该以固定字母表中的符号数量成指数形式运行（或者在该函数的某些函数中呈指数形式）！否则，对于无界字母来说，它也是多项式时间算法。因此，作为一名理论家，我将寻找仅在符号数量以及以某种方式有助于设计MF算法的情况下才能按时间指数计算的算法任务。另一方面，很可能不存在这种算法，并且在固定字母的情况下MF也是NP-hard的。

• 如果您对实际解决方案感兴趣，则近似解决方案可能会有所帮助。因此，在最坏的情况下，保证分解仅为最佳值的一半就不会太糟糕。

• 我想，没有给出可证明的近似比率但在实际环境中能很好地起作用的启发式方法也很有趣。

• 将问题实例转换为SAT或ILP实例应该不太困难，然后您可以运行SAT或ILP-Solver甚至获得最佳解决方案。

• 我的个人看法是，即使不知道MF的固定字母是否是NP困难的，也有足够的理论见解表明该问题足够困难，因此有理由寻找启发式解决方案等。在实际环境中运作良好。

参考书目：

[1] Anne Condon，JánManuch，Chris Thachuk：字符串分区的复杂性。J.离散算法32：24-43（2015）

[1b] Anne Condon，Jan Manuch，Chris Thachuk：碰撞感知字符串分配问题的复杂性及其与基因合成的寡核苷酸设计的关系。茧2008：265-275

[2] Henning Fernau，Florin Manea，Robert Mercas，Markus L. Schmid：带变量的模式匹配：快速算法和新的硬度结果。STACS 2015：302-315

[3] Markus L. Schmid：计算无相等和重复的字符串分解。理论。计算 科学 618：42-51（2016）

[4] Hideo Bannai，Travis Gagie，Innsaga Shunsuke，JuhaKärkkäinen，Dominik Kempa，Marcin Piatkowski，Shiho Sugimoto：多样的回文因式分解都是NP完全的。诠释 J.发现。计算 科学 29（2）：143-164（2018）

[5]亚伯拉罕·弗拉克斯曼（Abraham Flaxman），阿拉姆·威特罗斯·哈罗（Aram Wettroth Harrow），格雷戈里·B·索金（Gregory B. Sorkin）：具有最大不同子序列和子字符串的字符串。电器。J.梳 11（1）（2004）