Nombre maximal de sous-chaînes uniques d'une partition

J'ai modifié le titre pour qu'il soit plus compréhensible.

Voici une version détaillée de la question:

Nous avons une chaîne s et nous voulons la diviser en sous-chaînes . Chaque sous-chaîne est différente les unes des autres. Quel est le nombre maximum de sous-chaînes uniques que nous pouvons avoir d' une coupe. En d'autres termes, quel est le nombre maximum de sous-chaînes uniques qui concaténent pour se former s.

Voici quelques exemples:

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

Remarque : sne contient que des caractères minuscules. Je ne sais pas combien de temps set ne peux donc pas deviner la complexité temporelle optimale. :(

Est-ce un problème NP-difficile? Sinon, comment puis-je le résoudre efficacement?

J'ai entendu ce problème d'un de mes amis et je n'ai pas pu y répondre. J'essaie d'utiliser un Trie + gourmand pour résoudre ce problème. La méthode échoue pour le premier exemple.

Voici la solution Trie que j'ai trouvée:

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

Par exemple 1, le code ci-dessus renverra 3 car il essaie de se diviser sen a|ab|abaa.

Ajouter: Grâce à l'idée de tout le monde, il semble que ce problème soit très proche d'un problème NP. En ce moment, j'essaie de le penser dans cette direction. Supposons que nous ayons une fonction Guess(n). Cette fonction retournera Truesi nous pouvions trouver ndes sous-chaînes uniques à partir d'une division ou Falseautrement. Une observation ici est que si Guess(n) == True, alors Guess(i) == Truepour tous i <= n. Puisque nous pouvons fusionner deux sous-chaînes adjacentes ensemble. Cette observation peut conduire à une solution binaire. Cependant, cela nécessite encore que nous puissions calculer la Guessfonction très efficacement. Malheureusement, je ne pouvais toujours pas trouver de méthode polynomiale pour calculer Guess(n).

Ceci est connu sous le nom de problème de partition de chaîne sensible à la collision et il est démontré qu'il est NP-complet par une réduction de 3-SAT dans un article d'Anne Condon, Ján Maňuch et Chris Thachuk - Complexité d'un problème de partition de chaîne sensible à la collision et son relation avec la conception d'oligo pour la synthèse de gènes ( Conférence internationale sur l'informatique et la combinatoire , 265-275, 2008).

(Un grand merci à Gilad Barkan (גלעד ברקן) de m'avoir informé de cette discussion.)

Permettez-moi de partager mes réflexions sur ce problème d'un point de vue purement théorique (notez que j'utilise également "facteur" au lieu de "sous-mot").

Je pense qu'une définition suffisamment formelle du ou des problèmes considérés ici est la suivante:

Étant donné un mot w, trouvez les mots u_1, u_2, ..., u_k tels que

• u_i! = u_j pour chaque i, j avec 1 <= i <j <= k et
• u_1 u_2 ... u_k = w

Variante de maximisation (nous voulons plusieurs u_i): maximiser k

Variante de minimisation (nous voulons u_i court): minimiser max {| u_i | : 1 <= i <= k}

Ces problèmes deviennent des problèmes de décision en donnant en plus une borne B, qui, selon que nous parlons de la variable "plusieurs facteurs" ou de la variable "facteurs courts", est une borne inférieure sur k (nous voulons au moins B ou une borne supérieure sur max {| u_i | : 1 <= i <= k} (nous voulons des facteurs de longueur au plus B), respectivement. Pour parler de dureté NP, nous devons parler de problèmes de décision.

Utilisons les termes SF pour la variable "facteurs courts" et MF pour la variante "nombreux facteurs". En particulier, et c'est un point vraiment crucial, les problèmes sont définis de telle manière que nous obtenons un mot sur un alphabet qui n'est en aucune façon restreint. La version du problème était que nous savons a priori que nous ne récupérons que les mots d'entrée, disons que l'alphabet {a, b, c, d} est un problème différent! La dureté NP ne passe pas automatiquement de la variante "sans restriction" à la variante "alphabet fixe" (cette dernière peut être plus simple).

SF et MF sont des problèmes NP-complets. Cela a été montré dans [1, 1b] et [2], respectivement (comme Gilad l'a déjà souligné). Si je comprends bien la définition du problème informel (peut-être aussi) ici au début de cette discussion, alors le problème de cette discussion est exactement le problème MF. Il n'est pas mentionné au départ que les mots sont restreints pour provenir d'un alphabet fixe, plus tard on dit que nous pouvons supposer que seules les lettres minuscules sont utilisées. Si cela signifie que nous ne considérons que les mots sur l'alphabet fixe {a, b, c, ..., z}, alors cela changerait beaucoup en termes de dureté NP.

Un examen plus approfondi révèle certaines différences de complexité de SF et MF:

1. l'article [1, 1b] montre que SF reste NP-complet si nous fixons l'alphabet à un binaire (plus précisément: obtenir un mot w sur les lettres a et b et une borne B, peut-on le factoriser en facteurs de longueur distincts à la plupart des B?).
2. l'article [1, 1b] montre que SF reste NP-complet si nous fixons la borne B = 2 (plus précisément: en obtenant un mot w, pouvons-nous le factoriser en facteurs distincts de longueur au plus 2?).
3. l'article [3] montre que si à la fois l'alphabet et la borne B sont fixes, SF peut être résolu en temps polynomial.
4. l'article [2] montre que MF est NP-complet, mais seulement si l'alphabet n'est pas restreint ou fixé a priori! En particulier, il ne répond pas à la question si le problème est NP-complet si nous considérons uniquement les mots saisis sur un alphabet fixe (comme c'est généralement le cas dans les paramètres pratiques).
5. l'article [3] montre que MF peut être résolu en temps polynomial si les bornes d'entrée B sont à nouveau limitées par une constante, c'est-à-dire que le problème entré est un mot et une borne B de {1, 2, ..., K} , où K est une constante fixe.

Quelques commentaires sur ces résultats: Wrt (1) et (2), il est intuitivement clair que si l'alphabet est binaire, alors, pour rendre le problème SF difficile, la borne B ne peut pas être fixée aussi. Inversement, fixer B = 2 signifie que la taille de l'alphabet doit être assez grande pour produire des instances difficiles. En conséquence, (3) est plutôt trivial (en fait, [3] en dit un peu plus: on peut alors le résoudre en temps d'exécution non seulement polynomial, mais aussi | w | ^ 2 fois un facteur qui ne dépend que de la taille de l'alphabet et lié B). (5) n'est pas difficile non plus: si notre mot est long par rapport à B, alors nous pouvons obtenir la factorisation souhaitée en découpant simplement en facteurs de longueurs différentes. Sinon, alors nous pouvons forcer toutes les possibilités, ce qui n'est exponentiel que dans B, qui dans ce cas est supposé être une constante.

Donc, l'image que nous avons est la suivante: SF semble plus difficile, car nous avons la dureté même pour les alphabets fixes ou pour une borne fixe B. Le problème MF, d'autre part, devient résolu poly-temps si la borne est fixe (dans à cet égard, il est plus facile que SF), tandis que la question correspondante par rapport à la taille de l'alphabet est ouverte. MF est donc légèrement moins complexe que SF, même s'il s'avère que MF pour les alphabets fixes est également NP-complet. Cependant, s'il peut être démontré que MF peut être résolu pour des alphabets fixes en poly-temps, alors MF s'avère beaucoup plus facile que SF ... car le seul cas pour lequel il est difficile est quelque peu artificiel (alphabet illimité!) .

J'ai fait des efforts pour essayer de résoudre le cas de la MF avec un alphabet borné, mais je n'ai pas pu le régler et j'ai cessé de travailler dessus depuis. Je ne crois pas que d'autres chercheurs aient essayé très fort de le résoudre (donc ce n'est pas un de ces problèmes ouverts très difficiles, beaucoup de gens ont déjà essayé et échoué; je le considère en quelque sorte faisable). Je suppose que c'est aussi NP-difficile pour les alphabets fixes, mais peut-être que la réduction est si compliquée que vous obtiendrez quelque chose comme "MF est difficile pour les alphabets de taille 35 ou plus" ou quelque chose, ce qui ne serait pas super sympa non plus .

Concernant la littérature, je connais l'article [4], qui considère le problème de la division d'un mot w en facteurs distincts u_1, u_2, ..., u_k qui sont tous des palindromes, qui est également NP-complet.

J'ai jeté un rapide coup d'œil au papier [5], souligné par Gilad. Il semble cependant considérer un cadre différent. Dans cet article, les auteurs s'intéressent à la question combinatoire du nombre de sous-séquences ou sous-mots distincts qui peuvent être contenus dans un mot donné, mais ceux-ci peuvent se chevaucher. Par exemple, aaabaab contient 20 sous-mots différents a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (peut-être que je mal compté, mais vous avez l'idée). Certains d'entre eux n'ont qu'une seule occurrence, comme baa, certains plusieurs, comme aa. Dans tous les cas, la question n'est pas de savoir comment diviser le mot pour obtenir de nombreux facteurs distincts, car cela signifie que chaque symbole individuel contribue à exactement un facteur.

En ce qui concerne les solutions pratiques à ce genre de problèmes (gardez à l'esprit que je suis théoricien, alors prenez cela avec du grain de sel):

• À ma connaissance, il n'y a pas de bornes inférieures théoriques (comme la dureté NP) qui l'excluraient pour résoudre MF en temps polynomial si nous considérons uniquement les mots saisis sur un alphabet fixe. Il y a cependant une mise en garde: si vous obtenez un algorithme poly-temps, alors il devrait fonctionner de façon exponentielle dans le nombre de symboles de l'alphabet fixe (ou exponentiel dans une fonction de cela)! Sinon, ce serait aussi un algorithme de temps polynomial pour le cas des alphabets illimités. Donc, en tant que théoricien, je chercherais des tâches algorithmiques qui peuvent être calculées en exponentielle dans le temps uniquement si le nombre de symboles et qui aident en quelque sorte à concevoir un algorithme pour MF. D'un autre côté, il est probable qu'un tel algorithme n'existe pas et MF est également NP-difficile dans le cas de l'alphabet fixe.

• Si vous êtes intéressé par des solutions pratiques, il pourrait être utile d'approximer la solution. Il ne serait donc pas trop mauvais d'obtenir une factorisation garantie qui ne serait que la moitié de la valeur optimale dans le pire des cas.

• Heuristique qui ne donne pas un rapport d'approximation prouvable, mais qui fonctionne bien dans un cadre pratique serait également intéressant, je suppose.

• La transformation des instances de problème en instances SAT ou ILP ne devrait pas être trop difficile et vous pouvez alors exécuter un solveur SAT ou ILP pour obtenir même des solutions optimales.

• Mon opinion personnelle est que même si l'on ne sait pas si le cas de l'alphabet fixe de MF est NP-difficile, il y a suffisamment de connaissances théoriques qui suggèrent que le problème est suffisamment difficile pour qu'il soit justifié de rechercher des solutions heuristiques, etc. fonctionnent bien dans un cadre pratique.

Bibliographie:

[1] Anne Condon, Ján Manuch, Chris Thachuk: La complexité du partitionnement des chaînes. J. Algorithmes discrets 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Complexité d'un problème de partition de chaîne sensible aux collisions et sa relation avec la conception Oligo pour la synthèse des gènes. COCOON 2008: 265-275

[2] Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid: Pattern Matching with Variables: Fast Algorithms and New Hardness Results. STACS 2015: 302-315

[3] Markus L. Schmid: Calcul des factorisations de chaînes sans égalité et répétitives. Théor. Comput. Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: la factorisation palindromique diversifiée est NP-Complete. Int. J. Trouvé. Comput. Sci. 29 (2): 143-164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: Des cordes avec un maximum de sous-séquences et de sous-chaînes distinctes. Electr. J. Comb. 11 (1) (2004)

Voici une solution, mais elle explose très rapidement et n'est pas du tout proche d'une solution efficace. Il décompose d'abord la chaîne en une liste de sous-chaînes uniques sans souci de classement, puis tente d'utiliser itertools.permutation pour réassembler ces sous-chaînes dans la chaîne d'origine, testant CHAQUE permutation pour voir si elle correspond à la chaîne d'origine.

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

Pour le premier test, nous obtenons ceci:

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

Peut-être que cela peut être optimisé d'une manière ou d'une autre, mais cela prend quelques secondes sur cette machine.

J'ai essayé ce problème et y ai pensé en termes de l'opportunité de créer une partition à un index donné. Cette fonction est donc récursive et crée 2 branches à chaque index 1. Ne partitionnez pas à l'index i 2. Partitionnez à l'index i.

Sur la base de la partition, je remplis un ensemble, puis renvoie la taille de l'ensemble

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

Vous pouvez utiliser une fonction récursive avec un ensemble comme deuxième paramètre pour garder une trace des chaînes uniques dans le chemin actuel jusqu'à présent. Pour chaque récursivité, parcourez tous les indices plus 1 pour diviser la chaîne pour une chaîne candidate possible, et si la chaîne candidate n'est pas encore dans l'ensemble, effectuez un appel récursif avec la chaîne restante et le candidat ajouté à l'ensemble pour obtenir le nombre maximum de sous-chaînes uniques de la chaîne restante, ajoutez-y 1 et renvoyez le maximum des maximums des itérations. Renvoie 0 si la chaîne donnée est vide ou si toutes les chaînes candidates sont déjà dans l'ensemble:

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

Démo: https://repl.it/@blhsing/PriceyScalySphere

Dans Python 3.8, la logique ci-dessus peut également être écrite avec un appel à la maxfonction avec une expression de générateur qui filtre les candidats qui ont été "vus" avec une expression d'affectation:

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)

Voici une réponse basée sur la théorie des graphes.

Modélisation
Ce problème peut être modélisé comme un problème d'ensemble indépendant maximum sur un graphique de taille O(n²)comme suit:
Soit w = c_1, ..., c_nla chaîne d'entrée.
Laissez G = (V,E)un graphe non orienté, construit comme suit:
V = { (a, b) such that a,b in [1, n], a <= b }. Nous pouvons voir que la taille de Vest n(n-1)/2, où chaque sommet représente une sous-chaîne de w.
Ensuite, pour chaque couple de sommets (a1, b1)et (a2, b2), nous construisons l'arête ((a1, b1), (a2, b2))ssi
(i) [a1, b1]intersecte [a2, b2]ou
(ii) c_a1...c_b1 = c_a2...c_b2.
Autrement dit, nous construisons une arête entre deux sommets si (i) les sous-chaînes qu'ils représentent se chevauchent wou (ii) les deux sous-chaînes sont égales.

Nous pouvons alors voir pourquoi un ensemble maximum indépendant de Gfournit la réponse à notre problème.

Complexité
Dans le cas général, le problème de l'ensemble indépendant maximum (MIS) est NP-difficile, avec une complexité temporelle de O(1.1996^n)et dans l'espace polynomial [Xiao, NamaGoshi (2017)] .
Au début, je pensais que le graphique résultant serait un graphique en accords (pas de cycle induit de longueur> 3), ce qui aurait été très agréable depuis lors, le problème MIS peut être résolu en temps linéaire sur cette classe de graphiques.
Mais je me suis vite rendu compte que ce n'était pas le cas, il est assez facile de trouver des exemples où il y a des cycles induits de longueur 5 et plus.
En fait, le graphe résultant ne présente aucune propriété «agréable» que nous recherchons habituellement et qui permet de réduire la complexité du problème MIS à un problème polynomial.
Ce n'est qu'une limite supérieure de la complexité du problème, car la réduction du temps polynomial ne va que dans un sens (nous pouvons réduire ce problème au problème MIS, mais pas l'inverse, du moins pas trivialement). En fin de compte, nous finissons par résoudre ce problème O(1.1996^(n(n-1)/2))dans le pire des cas.
Donc, hélas, je n'ai pas pu prouver qu'il est en P, ou qu'il est NP-complet ou NP-dur. Une chose est sûre, c'est que le problème est dans NP, mais je suppose que ce n'est une surprise pour personne.

Implémentation
L'avantage de réduire ce problème au problème MIS est que le MIS est un problème classique, pour lequel plusieurs implémentations peuvent être trouvées, et que le problème MIS est également facilement écrit comme un ILP.
Voici une formulation ILP du problème MIS:

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

À mon avis, cela devrait être le moyen le plus efficace de résoudre ce problème (en utilisant cette modélisation comme problème MIS), car le solveur ILP est incroyablement efficace, en particulier lorsqu'il s'agit de grandes instances.

Il s'agit d'une implémentation que j'ai faite en utilisant Python3 et le solveur GLPK . Pour le tester, vous avez besoin d'un solveur LP compatible avec le format de fichier Cplex.

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

Vous pouvez ensuite les résoudre avec la glpsolcommande:
glpsol --lp LP_file_1
Le aababaase résout rapidement (0,02 sec sur mon ordinateur portable), mais comme prévu, les choses deviennent (beaucoup) plus difficiles à mesure que la taille de la chaîne augmente ...
Ce programme ne donne que la valeur numérique (et non la partition optimale), néanmoins la partition optimale et les sous-chaînes correspondantes peuvent être trouvées avec une implémentation similaire, en utilisant une interface solveur LP / python telle que pyomo

Temps et mémoire
aababaa : 0,02 seconde, 0,4 Mo, valeur: 4
kzshidfiouzh: 1,4 seconde, 3,8 Mo, valeur: 10
aababababbababab: 60,2 secondes, 31,5 Mo, valeur: 8
kzshidfiouzhsdjfyu: 207,5 secondes, 55,7 Mo, valeur: 14
Notez que le solveur LP propose également les limites inférieures et supérieures actuelles de la solution, donc pour le dernier exemple, je pourrais obtenir la solution réelle comme une limite inférieure après une minute.

Mon autre réponse était étroitement liée mais ne correspondait pas exactement à ce problème, laissant ambigu si la recherche de la plus grande factorisation de chaînes sans égalité pourrait être d'une classe de complexité différente que s'il existe une factorisation sans égalité avec une longueur de facteur liée (cette dernière traités par le document cité).

Dans l'article, Pattern matching with variables: Fast algorithms and new hardness results (Henning Fernau, Florin Manea, Robert Mercaş, and Markus L. Schmid, in Proc. 32nd Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 302–315, 2015), les auteurs montrent qu'il est NP-complet de décider, pour un nombre ket un mot donnés w, s'il wpeut être factorisé en kfacteurs distincts.

Si nous considérons le commentaire de templatetypedef , impliquant qu'il pourrait y avoir une solution temporelle polynomiale à la factorisation sans restriction et sans égalité la plus importante, alors nous pourrions sûrement utiliser un tel algorithme pour répondre si nous pouvions diviser la chaîne en kfacteurs distincts (sous-chaînes) en observant simplement si kest moins que le max que nous connaissons déjà.

Schmid (2016), cependant, écrit que "c'est toujours un problème ouvert que MaxEFF-s reste NP-complet si l'alphabet est fixé." (Calculer les factorisations de chaînes sans égalité et répétitives, Theoretical Computer Science Volume 618 , 7 mars 2016, Pages 42-51)

La taille maximale de factorisation sans égalité (MaxEFF-s) est cependant toujours paramétrée et est définie comme:

Instance: mot A wet un certain nombre m, 1 ≤ m ≤ |w|.

Question: Existe-t-il une factorisation p sans égal de wavec s(p) ≥ m? ( s(p)étant la taille de la factorisation.)