Quelle est la superstring la plus courte pour $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ k c \} $?

Question

dans Cet article sur pdf Page 3, ils donnent $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ k, (ab) ^ kc \} $ comme exemple d'entrée à l'algorithme gourmand pour les plus courtes superstring qui le fait avoir un rapport approximatif de 2.

Autant que je puisse dire, la superstring la plus courte de cet ensemble est soit $ C (AB) ^ kc (BA) ^ K $ ou $ B (AB) ^ kc (AB) ^ k $ - de toute façon, la longueur est 4k + 2 $ . Malheureusement, cela contredit la réclamation dans le document que gourmande génère une chaîne de longueur 2 fois supérieure à la superstring optimale.

• Sans perte de généralité, nous pouvons supposer que la gourmande ne produira jamais une chaîne plus longue que la concaténation de son ensemble d'entrée - si l'algorithme gourmand est réellement décrit de cette manière, nous pouvons simplement ajouter une instruction IF pour vérifier ce cas et retourner la concaténation à la place.
• La longueur de la concaténation des chaînes d'entrée est 6 000 $ + 2 $ .
• pour tout $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4K + 2} \ LE 1.5 $
• Par conséquent, soit le rapport approximatif pour tout algorithme raisonnable sur cette classe de problèmes doit être inférieur ou égal à 1,5, ou ce que je pense est le plus court Superstring n'est pas vraiment le plus court.

Quelqu'un peut-il expliquer pourquoi cette ligne d'argumentation ne fonctionne pas, soit de savoir ce que le plus court éventrage de cet ensemble est?

Answer 1

Un superstring plus court est $ C (AB) ^ {k + 1} C $ , qui a une longueur 2k $ 2k+4 $ .