Maximale Anzahl eindeutiger Teilzeichenfolgen einer Partition

Ich habe den Titel so geändert, dass er verständlicher ist.

Hier ist eine detaillierte Version der Frage:

Wir haben eine Zeichenfolge s und möchten sie in Teilzeichenfolgen aufteilen . Jeder Teilstring unterscheidet sich voneinander. Was ist die maximale Anzahl eindeutiger Teilzeichenfolgen, die wir aus einem Schnitt haben können? Mit anderen Worten, was ist die maximale Anzahl eindeutiger Teilzeichenfolgen, die sich zu einer Form verketten s.

Hier sind einige Beispiele:

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

Hinweis : sEnthält nur Kleinbuchstaben. Mir wird nicht gesagt, wie lange sund daher kann ich die optimale Zeitkomplexität nicht erraten. :((

Ist es ein NP-hartes Problem? Wenn nicht, wie kann ich es effizient lösen?

Ich habe dieses Problem von einem meiner Freunde gehört und konnte es nicht beantworten. Ich versuche, einen Trie + -Gier zu verwenden, um dieses Problem zu lösen. Die Methode schlägt für das erste Beispiel fehl.

Hier ist die Trie-Lösung, die ich mir ausgedacht habe:

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

Zum Beispiel 1, wird der obige Code 3 zurückkehren , da sie zu Split versuchen sin a|ab|abaa.

Hinzufügen: Dank der Idee aller sieht es so aus, als ob dieses Problem einem NP-Problem sehr nahe kommt. Im Moment versuche ich es aus dieser Richtung zu denken. Angenommen, wir haben eine Funktion Guess(n). Diese Funktion wird zurückgegeben, Truewenn wir neindeutige Teilzeichenfolgen aus einem Split oder auf Falseandere Weise finden konnten. Eine Beobachtung hier ist, dass wenn Guess(n) == True, dann Guess(i) == Truefür alle i <= n. Da können wir zwei benachbarte Teilzeichenfolgen zusammenführen. Diese Beobachtung kann zu einer binären Lösung führen. Es erfordert jedoch immer noch, dass wir die GuessFunktion sehr effizient berechnen können . Leider konnte ich immer noch keinen polynomiellen Berechnungsweg finden Guess(n).

Dies ist als kollisionsbewusstes String-Partitionsproblem bekannt und wird durch eine Reduktion von 3-SAT in einem Artikel von Anne Condon, Ján Maňuch und Chris Thachuk - Komplexität eines kollisionsbewussten String-Partitionsproblems und seiner Probleme als NP-vollständig gezeigt Beziehung zum Oligo-Design für die Gensynthese ( International Computing and Combinatorics Conference , 265-275, 2008).

(Vielen Dank an Gilad Barkan (גלעד ברקן), der mich auf diese Diskussion aufmerksam gemacht hat.)

Lassen Sie mich meine Gedanken zu diesem Problem aus rein theoretischer Sicht teilen (beachten Sie, dass ich anstelle von "Unterwort" auch "Faktor" verwende).

Ich denke, eine ausreichend formale Definition des Problems (oder der Probleme), die hier betrachtet wird, ist die folgende:

Finden Sie bei einem gegebenen Wort w die Wörter u_1, u_2, ..., u_k so, dass

• u_i! = u_j für jedes i, j mit 1 <= i <j <= k und
• u_1 u_2 ... u_k = w

Maximierungsvariante (wir wollen viele u_i): maximiere k

Minimierungsvariante (wir wollen kurz u_i): minimiere max {| u_i | : 1 <= i <= k}

Diese Probleme werden zu Entscheidungsproblemen, indem zusätzlich eine Grenze B angegeben wird, die je nachdem, ob es sich um die Variante "Viele Faktoren" oder die Variante "Kurzfaktoren" handelt, eine Untergrenze für k ist (wir wollen mindestens B. Faktoren) oder eine Obergrenze für max {| u_i | : 1 <= i <= k} (wir wollen höchstens Längenfaktoren B). Um über NP-Härte zu sprechen, müssen wir über Entscheidungsprobleme sprechen.

Verwenden wir die Begriffe SF für die "Short Factors" -Variante und MF für die "Many Factors" -Variante. Insbesondere, und dies ist ein wirklich entscheidender Punkt, werden die Probleme so definiert, dass wir ein Wort über ein Alphabet erhalten, das in keiner Weise eingeschränkt ist. Die Problemversion, bei der wir a priori wissen, dass wir nur Eingabewörter über das Alphabet {a, b, c, d} erhalten, ist ein anderes Problem! Die NP-Härte überträgt sich nicht automatisch von der "uneingeschränkten" auf die "feste Alphabet" -Variante (letztere könnte einfacher sein).

Sowohl SF als auch MF sind NP-vollständige Probleme. Dies wurde in [1, 1b] bzw. [2] gezeigt (wie Gilad bereits betont hat). Wenn ich die (vielleicht auch) informelle Problemdefinition hier zu Beginn dieser Diskussion richtig verstehe, dann ist das Problem dieser Diskussion genau das Problem MF. Es wird zunächst nicht erwähnt, dass die Wörter nur aus einem festen Alphabet stammen dürfen. Später wird davon ausgegangen, dass nur Kleinbuchstaben verwendet werden. Wenn dies bedeutet, dass wir nur Wörter über dem festen Alphabet {a, b, c, ..., z} betrachten, würde sich dies tatsächlich in Bezug auf die NP-Härte stark ändern.

Ein genauerer Blick zeigt einige Unterschiede in der Komplexität von SF und MF:

1. Papier [1, 1b] zeigt, dass SF NP-vollständig bleibt, wenn wir das Alphabet auf ein binäres fixieren (genauer gesagt: Wenn wir ein Wort w über die Buchstaben a und b und ein gebundenes B erhalten, können wir es in verschiedene Längenfaktoren bei faktorisieren die meisten B?).
2. Papier [1, 1b] zeigt, dass SF NP-vollständig bleibt, wenn wir die Grenze B = 2 festlegen (genauer: Wenn wir ein Wort w erhalten, können wir es in unterschiedliche Längenfaktoren von höchstens 2 faktorisieren?).
3. Papier [3] zeigt, dass SF sowohl in Polynomzeit gelöst werden kann, wenn sowohl das Alphabet als auch das gebundene B festgelegt sind.
4. Papier [2] zeigt, dass MF NP-vollständig ist, aber nur, wenn das Alphabet nicht a priori eingeschränkt oder festgelegt ist! Insbesondere wird die Frage nicht beantwortet, ob das Problem NP-vollständig ist, wenn wir nur Eingabewörter über ein festes Alphabet betrachten (wie es in praktischen Einstellungen üblich ist).
5. Papier [3] zeigt, dass MF in Polynomzeit gelöst werden kann, wenn die Eingabegrenzen B wieder durch eine Konstante begrenzt sind, dh die Problemeingabe ist ein Wort und eine Grenze B aus {1, 2, ..., K} , wobei K eine feste Konstante ist.

Einige Kommentare zu diesem Ergebnis: In (1) und (2) ist intuitiv klar, dass, wenn das Alphabet binär ist, die Grenze B nicht ebenfalls festgelegt werden kann, um das Problem SF zu erschweren. Umgekehrt bedeutet das Festlegen von B = 2, dass die Alphabetgröße ziemlich groß werden muss, um schwierige Instanzen zu erzeugen. Infolgedessen ist (3) eher trivial (tatsächlich sagt [3] etwas mehr: Wir können es dann in der Laufzeit nicht nur polynomisch lösen, sondern auch | w | ^ 2 mal einen Faktor, der nur von der Alphabetgröße abhängt und gebunden B). (5) ist auch nicht schwierig: Wenn unser Wort im Vergleich zu B lang ist, können wir die gewünschte Faktorisierung erhalten, indem wir einfach in Faktoren unterschiedlicher Länge aufteilen. Wenn nicht, können wir alle Möglichkeiten brutal erzwingen, was nur in B exponentiell ist, was in diesem Fall als Konstante angenommen wird.

Das Bild, das wir haben, ist das folgende: SF scheint schwieriger zu sein, weil wir selbst für feste Alphabete oder für eine feste Grenze B eine Härte haben. Das Problem MF wird andererseits mehrfach lösbar, wenn die Grenze fest ist (in diesbezüglich ist es einfacher als SF), während die entsprechende Frage zur Alphabetgröße offen ist. MF ist also etwas weniger komplex als SF, auch wenn sich herausstellt, dass MF für feste Alphabete ebenfalls NP-vollständig ist. Wenn jedoch gezeigt werden kann, dass MF in Poly-Zeit für feste Alphabete gelöst werden kann, ist MF viel einfacher als SF ... weil der eine Fall, für den es schwierig ist, etwas künstlich ist (unbegrenztes Alphabet!). .

Ich habe einige Anstrengungen unternommen, um den Fall von MF mit begrenztem Alphabet zu lösen, aber ich konnte es nicht regeln und habe seitdem aufgehört, daran zu arbeiten. Ich glaube nicht, dass andere Forscher sich sehr bemüht haben, es zu lösen (dies ist also nicht eines dieser sehr schwierigen offenen Probleme, viele Menschen haben es bereits versucht und sind gescheitert; ich halte es irgendwie für machbar). Ich würde vermuten, dass es auch für feste Alphabete NP-schwer ist, aber vielleicht ist die Reduzierung so kompliziert, dass Sie so etwas wie "MF ist schwer für Alphabete der Größe 35 oder größer" oder so etwas bekommen würden, was auch nicht besonders schön wäre .

In Bezug auf weitere Literatur kenne ich die Arbeit [4], in der das Problem der Aufteilung eines Wortes w in verschiedene Faktoren u_1, u_2, ..., u_k betrachtet wird, die alle Palindrome sind, was ebenfalls NP-vollständig ist.

Ich warf einen kurzen Blick auf Papier [5], auf das Gilad hingewiesen hatte. Es scheint jedoch eine andere Einstellung zu berücksichtigen. In diesem Artikel interessieren sich die Autoren für die kombinatorische Frage, wie viele verschiedene Teilsequenzen oder Unterwörter in einem bestimmten Wort enthalten sein können, aber diese können sich überschneiden. Zum Beispiel enthält aaabaab 20 verschiedene Unterwörter a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (vielleicht ich) falsch gezählt, aber Sie bekommen die Idee). Einige von ihnen haben nur ein Vorkommen, wie baa, einige mehrere, wie aa. Auf jeden Fall ist die Frage nicht, wie wir das Wort irgendwie aufteilen können, um viele verschiedene Faktoren zu erhalten, da dies bedeutet, dass jedes einzelne Symbol zu genau einem Faktor beiträgt.

In Bezug auf praktische Lösungen für diese Art von Problemen (denken Sie daran, dass ich ein Theoretiker bin, nehmen Sie dies also mit Salzkorn):

• Meines Wissens gibt es keine theoretischen Untergrenzen (wie die NP-Härte), die es ausschließen würden, MF in Polynomzeit zu lösen, wenn wir nur Eingabewörter über ein festes Alphabet betrachten. Es gibt jedoch eine Einschränkung: Wenn Sie einen Poly-Time-Algorithmus erhalten, sollte dieser exponentiell in der Anzahl der Symbole aus dem festen Alphabet ausgeführt werden (oder in einer Funktion davon exponentiell)! Andernfalls wäre es auch ein Polynomzeitalgorithmus für den Fall unbegrenzter Alphabete. Als Theoretiker würde ich also nach algorithmischen Aufgaben suchen, die nur dann in der Zeit exponentiell berechnet werden können, wenn die Anzahl der Symbole und irgendwie dazu beitragen, einen Algorithmus für MF zu entwickeln. Andererseits ist es wahrscheinlich, dass ein solcher Algorithmus nicht existiert und MF im Fall des festen Alphabets auch NP-hart ist.

• Wenn Sie an praktischen Lösungen interessiert sind, kann es hilfreich sein, die Lösung zu approximieren. Eine Faktorisierung zu erhalten, die garantiert nur halb so groß ist wie das Optimum im schlimmsten Fall, wäre also nicht schlecht.

• Interessant wären auch Heuristiken, die kein nachweisbares Näherungsverhältnis liefern, aber in der Praxis gut funktionieren.

• Das Umwandeln der Probleminstanzen in SAT- oder ILP-Instanzen sollte nicht zu schwierig sein. Anschließend können Sie einen SAT- oder ILP-Solver ausführen, um sogar optimale Lösungen zu erhalten.

• Meine persönliche Meinung ist, dass, obwohl nicht bekannt ist, ob der Fall des MF mit festem Alphabet NP-schwer ist, es genügend theoretische Erkenntnisse gibt, die darauf hindeuten, dass das Problem schwer genug ist, so dass es gerechtfertigt ist, nach heuristischen Lösungen usw. zu suchen arbeiten gut in einer praktischen Umgebung.

Literaturverzeichnis:

[1] Anne Condon, Ján Manuch und Chris Thachuk: Die Komplexität der String-Partitionierung. J. Discrete Algorithms 32: 24 & ndash; 43 (2015)

[1b] Anne Condon, Ján Manuch und Chris Thachuk: Komplexität eines kollisionsbewussten String-Partitionsproblems und seine Beziehung zum Oligo-Design für die Gensynthese. COCOON 2008: 265 & ndash; 275

[2] Henning Fernau, Florin Manea, Markus L. Schmid, Robert Mercas: Mustervergleich mit Variablen: Schnelle Algorithmen und neue Härteergebnisse. STACS 2015: 302–315

[3] Markus L. Schmid: Berechnung gleichheitsfreier und sich wiederholender String-Faktorisierungen. Theor. Comput. Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski und Shiho Sugimoto: Die vielfältige palindromische Faktorisierung ist NP-vollständig. Int. J. gefunden. Comput. Sci. 29 (2): 143 & ndash; 164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: Saiten mit maximal vielen unterschiedlichen Folgen und Teilzeichenfolgen. Electr. J. Comb. 11 (1) (2004)

Hier ist eine Lösung, die jedoch sehr schnell explodiert und bei weitem keine effiziente Lösung darstellt. Zunächst wird die Zeichenfolge in eine Liste eindeutiger Teilzeichenfolgen ohne Bedenken hinsichtlich der Reihenfolge zerlegt. Anschließend wird versucht, diese Teilzeichenfolgen mithilfe von itertools.permutation wieder zu der ursprünglichen Zeichenfolge zusammenzusetzen. Dabei wird JEDE Permutation getestet, um festzustellen, ob sie mit der ursprünglichen Zeichenfolge übereinstimmt.

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]}")

Für den ersten Test erhalten wir Folgendes:

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

Vielleicht kann dies irgendwie optimiert werden, aber das dauert auf dieser Maschine einige Sekunden.

Ich habe dieses Problem ausprobiert und darüber nachgedacht, ob eine Partition an einem bestimmten Index erstellt werden soll. Diese Funktion ist also rekursiv und erstellt 2 Zweige an jedem Index 1. Partitionieren Sie nicht am Index i 2. Partitionieren Sie am Index i.

Basierend auf der Partition fülle ich eine Menge aus und gebe dann die Größe der Menge zurück

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([]))

https://onlinegdb.com/HJynWw-iH

Sie können eine rekursive Funktion mit einem Satz als zweitem Parameter verwenden, um die eindeutigen Zeichenfolgen im aktuellen Pfad zu verfolgen. Durchlaufen Sie für jede Rekursion alle Indizes plus 1, um die Zeichenfolge für eine mögliche Kandidatenzeichenfolge aufzuteilen. Wenn die Kandidatenzeichenfolge noch nicht im Satz enthalten ist, führen Sie einen rekursiven Aufruf mit der verbleibenden Zeichenfolge und dem zum Satz hinzugefügten Kandidaten durch Um die maximale Anzahl eindeutiger Teilzeichenfolgen aus der verbleibenden Zeichenfolge zu erhalten, fügen Sie 1 hinzu und geben Sie das Maximum der Maximalwerte aus den Iterationen zurück. Geben Sie 0 zurück, wenn entweder die angegebene Zeichenfolge leer ist oder alle Kandidatenzeichenfolgen bereits im Satz enthalten sind:

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

Demo: https://repl.it/@blhsing/PriceyScalySphere

In Python 3.8 kann die obige Logik auch mit einem Aufruf der maxFunktion mit einem Generatorausdruck geschrieben werden, der Kandidaten filtert, die mit einem Zuweisungsausdruck "gesehen" wurden:

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)

Hier ist eine graphentheoretische Antwort.

Modellierung
Dieses Problem kann O(n²)wie folgt als maximales unabhängiges Mengenproblem in einem Diagramm mit einer Größe modelliert werden:
Sei w = c_1, ..., c_ndie Eingabezeichenfolge.
Sei G = (V,E)ein ungerichteter Graph, der wie folgt aufgebaut ist :
V = { (a, b) such that a,b in [1, n], a <= b }. Wir können sehen, dass die Größe von Vist n(n-1)/2, wobei jeder Scheitelpunkt eine Teilzeichenfolge von darstellt w.
Dann bauen wir für alle paar Eckpunkte (a1, b1)und (a2, b2)die Kante, ((a1, b1), (a2, b2))wenn
(i) [a1, b1]schneidet [a2, b2]oder
(ii) c_a1...c_b1 = c_a2...c_b2.
Anders gesagt, wir bauen eine Kante zwischen zwei Eckpunkten, wenn (i) die Teilzeichenfolgen, die sie darstellen, sich überlappen woder (ii) die beiden Teilzeichenfolgen gleich sind.

Wir können dann sehen , warum eine maximale unabhängige Menge von Gder Antwort auf unser Problem bietet.

Komplexität
Im allgemeinen Fall ist das MIS-Problem (Maximum Independent Set) NP-hart mit einer zeitlichen Komplexität von O(1.1996^n)und im Polynomraum [Xiao, NamaGoshi (2017)] .
Zuerst dachte ich, dass der resultierende Graph ein Akkordgraph sein würde (kein induzierter Zyklus mit einer Länge> 3), was sehr schön gewesen wäre, da seitdem das MIS-Problem in linearer Zeit auf dieser Klasse von Graphen gelöst werden kann.
Aber mir wurde schnell klar, dass dies nicht der Fall ist. Es ist ziemlich einfach, Beispiele zu finden, bei denen es zu induzierten Zyklen mit einer Länge von 5 und mehr kommt.
Tatsächlich weist der resultierende Graph keine 'nette' Eigenschaft auf, nach der wir normalerweise suchen, und die es ermöglicht, die Komplexität des MIS-Problems auf ein Polynom zu reduzieren.
Dies ist nur eine Obergrenze für die Komplexität des Problems, da die Polynomzeitreduktion nur in eine Richtung verläuft (wir können dieses Problem auf das MIS-Problem reduzieren, aber nicht umgekehrt, zumindest nicht trivial). Letztendlich lösen wir dieses Problem im O(1.1996^(n(n-1)/2))schlimmsten Fall.
Leider konnte ich nicht beweisen, dass es in P ist oder dass es NP-vollständig oder NP-hart ist. Eine sichere Sache ist, dass das Problem in NP liegt, aber ich denke, das ist für niemanden eine Überraschung.

Implementierung
Der Vorteil der Reduzierung dieses Problems auf das MIS-Problem besteht darin, dass das MIS ein klassisches Problem ist, für das mehrere Implementierungen gefunden werden können, und dass das MIS-Problem auch leicht als ILP geschrieben werden kann.
Hier ist eine ILP-Formulierung des MIS-Problems:

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

Meiner Meinung nach sollte dies der effizienteste Weg sein, um dieses Problem zu lösen (unter Verwendung dieser Modellierung als MIS-Problem), da ILP-Solver unglaublich effizient sind, insbesondere wenn es um große Instanzen geht.

Dies ist eine Implementierung, die ich mit Python3 und dem GLPK- Solver durchgeführt habe. Zum Testen benötigen Sie einen LP-Solver, der mit dem Cplex-Dateiformat kompatibel ist.

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')

Sie können sie dann mit dem glpsolBefehl lösen :
glpsol --lp LP_file_1
Das aababaawird schnell gelöst (0,02 Sekunden auf meinem Laptop), aber wie erwartet werden die Dinge (viel) schwieriger, wenn die Zeichenfolgengröße zunimmt ....
Dieses Programm gibt nur den numerischen Wert an (und nicht die optimale Partition), dennoch können die optimale Partition und die entsprechenden Teilzeichenfolgen mit einer ähnlichen Implementierung unter Verwendung einer LP-Solver / Python-Schnittstelle wie Pyomo gefunden werden

Zeit und Speicher
aababaa : 0,02 Sekunden, 0,4 MB, Wert: 4
kzshidfiouzh: 1,4 Sekunden, 3,8 MB, Wert: 10
aababababbababab: 60,2 Sekunden, 31,5 MB, Wert: 8
kzshidfiouzhsdjfyu: 207,5 Sekunden, 55,7 MB, Wert: 14
Beachten Sie, dass der LP-Solver auch bietet die aktuellen unteren und oberen Grenzen der Lösung, so dass ich für das letzte Beispiel die tatsächliche Lösung nach einer Minute als untere Grenze erhalten könnte.

Meine andere Antwort war eng verwandt, entsprach aber nicht genau diesem Problem, so dass nicht eindeutig ist, ob das Finden der größten gleichheitsfreien String-Faktorisierung einer anderen Komplexitätsklasse angehört als die Frage, ob es eine gleichheitsfreie Faktorisierung mit gebundener Faktorlänge gibt (letztere durch das zitierte Papier angesprochen werden).

In der Arbeit Pattern Matching mit Variablen: Schnelle Algorithmen und neue Härteergebnisse (Henning Fernau, Florin Manea, Robert Mercaş und Markus L. Schmid, Proc. 32. Symposium über theoretische Aspekte der Informatik, STACS 2015, Band 30 von Leibniz International Proceedings in Informatics (LIPIcs) , S. 302–315, 2015) zeigen die Autoren, dass es NP-vollständig ist, für eine bestimmte Zahl kund ein bestimmtes Wort zu entscheiden w, ob win kverschiedene Faktoren zerlegt werden kann.

Wenn wir den Kommentar von templatetypedef betrachten , der impliziert, dass es eine polynomielle Zeitlösung für die uneingeschränkte, größte gleichheitsfreie Faktorisierung geben könnte, dann könnten wir sicherlich einen solchen Algorithmus verwenden, um zu antworten, ob wir den String in kverschiedene Faktoren (Teilzeichenfolgen) aufteilen könnten, indem wir einfach beobachten, ob dies der Fall kist weniger als das Maximum, das wir bereits kennen.

Schmid (2016) schreibt jedoch: "Es ist immer noch ein offenes Problem, ob MaxEFF-s NP-vollständig bleibt, wenn das Alphabet festgelegt ist." (Berechnung gleichheitsfreier und sich wiederholender String-Faktorisierungen, Theoretical Computer Science Volume 618 , 7. März 2016, Seiten 42-51)

Die maximale gleichheitsfreie Faktorisierungsgröße (MaxEFF-s) ist jedoch weiterhin parametrisiert und wie folgt definiert:

Instanz: Ein Wort wund eine Zahl m, 1 ≤ m ≤ |w|.

Frage: Gibt es eine gleichheitsfreie Faktorisierung p von wmit s(p) ≥ m? ( s(p)ist die Größe der Faktorisierung.)