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

## string algorithm (5)

Example 1
s = 'aababaa'
output = 4
Explain: we can split it 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

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

def max_unique_substrings(s, seen=()):
maximum = 0
for i in range(1, len(s) + 1):
candidate = s[:i]
if candidate not in seen:
maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen}))
return maximum

def max_unique_substrings(s, seen=()):
return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

def max(a,b):
if a>b: return a
return b

def keep(last, current, inp, map):
# print last
# print current
# print map

if len(inp) == 2 :
if inp[0]==inp[1]: return 1
return 2

if current >= len(inp):
return len(map)
// This is when we are at the start of the string.
// In this case we can only do one thing not partition and thus take the entire string as a possible string.

if current == last :
map11 = map.copy()
map11.add(inp[current:])
return keep(last, current + 1, inp, map11)

map1 = map.copy();
if current != (len(inp)-1):
map1.add(inp[last:current])

map2 = map.copy()

return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1))

print keep(0,0,"121", set([]))
print keep(0,0,"aaaaaaa", set([]))
print keep(0,0,"aba", set([]))
print keep(0,0,"aababaa", set([]))
print keep(0,0,"21", set([]))
print keep(0,0,"22", set([]))

w = c_1, ..., c_n 为输入字符串。
G = (V,E) 是无向图，其构建如下：
V = { (a, b) such that a,b in [1, n], a <= b } 。 我们可以看到 V 的大小为 n(n-1)/2 ，其中每个顶点代表 w 的子串。

（i） [a1, b1] 相交 [a2, b2]
（ii） c_a1...c_b1 = c_a2...c_b2

Objective function
maximize sum(X[i], i in 1..n)
Constraints:
for all i in 1..n, X[i] in {0, 1}
for all edge (i, j), X[i] + X[j] <= 1

from itertools import combinations

def edges_from_string(w):
# build vertices
vertices = set((a, b) for b in range(len(w)) for a in range(b+1))
# build edges
edges = {(a, b): set() for (a, b) in vertices}
for (a1, b1), (a2, b2) in combinations(edges, 2):
# case: substrings overlap
if a1 <= a2 <= b1:
edges[(a1, b1)].add((a2, b2))
if a2 <= a1 <= b2:
edges[(a2, b2)].add((a1, b1))
# case: equal substrings
if w[a1:b1+1] == w[a2:b2+1]:
if a1 < a2:
edges[(a1, b1)].add((a2, b2))
else:
edges[(a2, b2)].add((a1, b1))
return edges

def write_LP_from_edges(edges, filename):
with open(filename, 'w') as LP_file:
LP_file.write('Maximize Z: ')
LP_file.write("\n".join([
"+X%s_%s" % (a, b)
for (a, b) in edges
]) + '\n')
LP_file.write('\nsubject to \n')
for (a1, b1) in edges:
for (a2, b2) in edges[(a1, b1)]:
LP_file.write(
"+X%s_%s + X%s_%s <= 1\n" %
(a1, b1, a2, b2)
)
LP_file.write('\nbinary\n')
LP_file.write("\n".join([
"X%s_%s" % (a, b)
for (a, b) in edges.keys()
]))
LP_file.write('\nend\n')
write_LP_from_edges(edges_from_string('aababaa'), 'LP_file_1')
write_LP_from_edges(edges_from_string('kzshidfiouzh'), 'LP_file_2')

glpsol --lp LP_file_1
aababaa 很快就解决了（在我的笔记本电脑上为0.02秒），但是正如预期的那样，随着字符串大小的增加，事情变得（非常）艰难。

aababaa ：0.02秒，0.4 MB，值：4
kzshidfiouzh ：1.4秒，3.8 MB，值：10
aababababbababab ：60.2秒，31.5 MB，价值：8
kzshidfiouzhsdjfyu ：207.5秒，55.7 MB，值：14

import itertools as it

def splitter(seq):
temp = [seq]
for x in range(1, len(seq)):
print(seq[:x], seq[x:])
temp.append(seq[:x])
temp.append(seq[x:])
return temp

if __name__ == "__main__":
test = input("Enter a string: ")
temp = splitter(test)
copy = temp[::]
condition = True
for x in temp:
if len(x) > 1:
copy.extend(splitter(x))
copy = sorted(list(set(copy)))
print(copy)
count = []
for x in range(len(test)):
item = it.permutations(copy, x)
try:
while True:
temp = next(item)
if "".join(list(temp)) == test:
if len(temp) == len(set(temp)):
count.append((len(temp), temp))
except StopIteration:
print('next permutation begin iteration')
continue
print(f"All unique splits: {count}")
print(f"Longest unique split : {max(count)[0]}")

All unique splits: [(1, ('aababaa',)), (2, ('a', 'ababaa')), (2, ('aa', 'babaa')), (2,
('aab', 'abaa')), (2, ('aaba', 'baa')), (2, ('aabab', 'aa')), (2, ('aababa', 'a')), (3,
('a', 'ab', 'abaa')), (3, ('a', 'aba', 'baa')), (3, ('a', 'abab', 'aa')), (3, ('aa', 'b',
'abaa')), (3, ('aa', 'ba', 'baa')), (3, ('aa', 'baba', 'a')), (3, ('aab', 'a', 'baa')),
(3, ('aab', 'ab', 'aa')), (3, ('aab', 'aba', 'a')), (3, ('aaba', 'b', 'aa')), (3,
('aaba', 'ba', 'a')), (4, ('a', 'aba', 'b', 'aa')), (4, ('aa', 'b', 'a', 'baa')), (4,
('aa', 'b', 'aba', 'a')), (4, ('aab', 'a', 'b', 'aa'))]
Longest unique split : 4

（非常感谢吉拉德·巴尔坎（Gilad Barkan）使我意识到了这一讨论。）

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

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

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是某个固定常数。

• 据我所知，如果我们只考虑固定字母上的输入单词，那么就没有理论上的下界（例如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. 电器。 J.梳 11（1）（2004）