# 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()
return keep(last, current + 1, inp, map11)

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

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:
if a2 <= a1 <= b2:
# case: equal substrings
if w[a1:b1+1] == w[a2:b2+1]:
if a1 < a2:
else:
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``````

• u_i！= u_j對於每個i，j的1 <= i <j <= k
• u_1 u_2 ... u_k = w

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·索金（Gregory B. Sorkin）：具有最大不同子序列和子字符串的字符串。 電器。 J.梳 11（1）（2004）