(Merci à Greg0ire ci-dessous pour aider avec les concepts clés)
Le défi: Construire un programme qui trouve toutes les substrings et les "balises" avec des attributs de couleur (en les surlignant efficacement dans XML). p>
Les règles: p>
thesubstring tag #> code> où # code> est un nombre positif unique à cette sous-chaîne et de substrings identiques. LI>
- La priorité de l'algorithme est de trouver la plus longue sous-chaîne, pas combien de fois il correspond dans le texte. Li>
ol>
Remarque: l'ordre du marquage indiqué dans l'exemple ci-dessous n'est pas important. Sa juste utilisée par l'OP pour la clarté. P>
Un exemple d'entrée: p> xxx pré>
une sortie partiellement correcte (OP peut ne pas avoir Complètement remplacé parfaitement dans cet exemple) P>
<TAG1>hello</TAG1>!<TAG2>TAG</TAG2>!<TAG3></</TAG3><TAG1>hello</TAG1>.<TAG2>TAG</TAG2>.<TAG3></</TAG3>
7 Réponses :
L'étape est décrite sur cette page: http://en.wikipedia.org/wiki/longest_common_substring_problem
Et voici une implémentation PHP: http: // www. davidtavarez.com/archives/longer-common-substring-problem-php-implementatation/ (vous devrez le réparer, il contient des entités HTML et le commentaire dit qu'il renvoie un entier mais nous ne savons pas Ce qu'il représente ...), si cela ne fonctionne toujours pas, vous pouvez essayer de mettre en œuvre le pseudo-code de Wikipedia. Je pense que vous pouvez utiliser Retour Références Pour faire cela. Voir ce message: Expression régulière pour détecter la répétition dans une chaîne
J'ai fait de nombreuses tentatives et pour le moment où j'ai cette expression: # (a-za-z] +). * \ 1 #, mais je pense qu'il trouve la première chaîne répétée, pas la plus grande ...
C'était avant que je sache que vous vous souciez de mots ...
Ce que vous devriez faire est:
Pensez-vous que c'est de la peine de poster cela comme un défi de golf de code ??
Tomit avait posté une réponse intervérante concernant la recherche et remplacer la fonction pour coloriser la chaîne, mais semble-t-elle l'avoir retirée, probablement parce qu'il pensait que c'était hors-pied. Peu importe, ce n'est pas très difficile à faire avec Str_replace. Pour le golf du code, vous pourriez essayer ou vous pouvez même offrir une prime pour cette question ...
^ Str_replace donne une sortie incorrecte pour certaines entrées (au moins si elle est faite naïvement).
Cela ne couvre pas les cordes de longueur 2, seulement 3 et plus
Tagged "OK" au lieu de "Ook" à Loremipsum (voir le dernier mot)
Le nombre de caractères est 343 en utilisant Un algorithme exponentiel, alors qu'il est 344 lors de l'utilisation d'un algorithme quadratique.
Le code posté est le quadratique. Pour l'algorithme exponentiel, changez l'occurrence de Entrée 1: sortie 1: entrée 2: sortie 2: init = << queues à des sous-séquences dans le code.
Vous devriez être capable de resserrer votre algorithme de manière à ce qu'il puisse courir contre l'exemple de problème à un délai raisonnable - voir qu'il y a au moins une autre solution qui ne s'appuie pas sur Regex Magic
Venez penser à cela, en utilisant inits = << queues x est un seul caractère de plus que des sous-séquences x , encore une fois de temps polynomial. La peine ou pas? (Think Code-Golf!)
et le résultat de l'exécution de celui-ci sur l'exemple d'entrée, il choisit les mots suivants ('loremipsum', "Dummytext", "industrie", "print", "types", "oft", "ing", "et", ",", "Ook '," SS "," IM "," ',' fr ',' er ',' le ',' pe ') et le résultat est: qui est plus lisible sur ce wiki en surbrillance Comme ceci: loremipsum i ss im pli mannequin OFT il impression ing et types e tt ing industrie . loremipsum hasibe fr industrie ' ss t et ard mannequintext ev er depuis le 1500S, w < KBD> HE Nanunknown Imprimer ER T OOK Agal LE Y OFT Y pe et scrabam le di tt omakea types pe < / KBD> C IM EN B OO k . ps. Quelqu'un s'est plaint, alors j'ai ajouté des déclarations d'entrée et de sortie. À la confusion, je m'excuse - cela me semblait évident. Apparemment pas, j'ai ajouté des instructions de préfixes / remorques, qui ne sont pas requises par la spécification de problème et ne doivent pas être comptées sur la longueur du code.
Que signifie la gamme (32) ici? Cela signifie-t-il que cela ne peut gérer que jusqu'à une longueur de 32 caractères (désolé ne peut pas lire Python ... encore!)
-1: Ne suit pas les spécifications, s est indéfini et aucune sortie, même si S est défini.
@Trinithis: La spécification ne demande pas d'E / S d'être effectuée, d'où mon code prend une chaîne s comme entrée et la sortie est renvoyée dans s . Vous pouvez appeler ces coins coupants si vous le souhaitez, mais vous ne pouvez pas dire que cela ne suit pas les spécifications! Voir la solution Perl, il ne compte pas non plus l'entrée / la sortie.
Ce que je voulais dire sur des spécifications est que vous utilisez
@TRINITHIS: J'ai compris que "le marquage doit être de la forme
Vous n'avez pas ta tagué "im" dans simplement et spécimen
@ M42: Vous aviez raison, merci d'avoir souligné - il y avait un bug. Je l'ai réparé, ainsi que les résultats.
fait un ensemble sorties, comme prévu: p> M code> de toutes les 2 chaînes de caractères est alors itérate à travers leur de les assigner dans l'ordre gourmand de longueur p>
<TAG1>LoremIpsum</TAG1>i<TAG11>ss</TAG11><TAG15>im</TAG15>ply<TAG2>dummytext</TAG2><TAG13>of</TAG13><TAG6>the</TAG6><TAG5>print</TAG5><TAG8>ing</TAG8><TAG9>and</TAG9><TAG4>types</TAG4>e<TAG10>tt</TAG10><TAG8>ing</TAG8><TAG3>industry</TAG3>.<TAG1>LoremIpsum</TAG1>hasbe<TAG17>en</TAG17><TAG6>the</TAG6><TAG3>industry</TAG3>'<TAG11>ss</TAG11>t<TAG9>and</TAG9>ard<TAG2>dummytext</TAG2>ev<TAG16>er</TAG16>since<TAG6>the</TAG6>1500s,wh<TAG17>en</TAG17>anunknown<TAG5>print</TAG5><TAG16>er</TAG16>t<TAG7>ook</TAG7>agal<TAG14>le</TAG14>y<TAG13>of</TAG13>ty<TAG12>pe</TAG12><TAG9>and</TAG9>scramb<TAG14>le</TAG14>di<TAG10>tt</TAG10>omakea<TAG4>types</TAG4><TAG12>pe</TAG12>c<TAG15>im</TAG15><TAG17>en</TAG17>b<TAG7>ook</TAG7>.
Code pause avec abcd1tagabcd2tag
ERRR, problème: voir comment dans
Pas pur fonctionnel / pas court / pas beau / beaucoup d'effets secondaires /
Merci beaucoup à Dennis Williamson qui m'a aidé à arriver à cette approche en répondant à quelques questions connexes que j'avais sur Script de shell - ici et ici .
problèmes connus avec ci-dessous: p>
Comme vous pouvez le constater, c'est une énorme méthode de force brute - pas un algorithme intelligent du tout. J'ai enregistré le temps pris pour quelques exemples de fichiers. P>
sh tagwords4 sample2.txt
+1 question très intéressante. Allez-vous chercher les plus grandes pièces de texte répétées ou pour les morceaux de texte les plus répétés? Comment allez-vous nommer un "morceau de texte" (pour moi, c'est un groupe de mots consécutifs)? Une expression"?
Bonjour Greg - merci de demander ... J'en ai en fait besoin pour toute chaîne d'octets en fait et la "plus grande" chaîne ... :)
Salut rubicon10. Si vous acceptez des réponses dans toutes les langues, vous voudrez peut-être ajouter les balises langue-agnostic et Rosetta-pierre. Aussi: la solution la plus élégante n'est pas vraiment du code de golf dans ma définition ;-) -
Les tests d'éloquence sont 1. pas [Code-golf] 2. Très subjectif et 3. Non couvert par le Remise spéciale qui a été faite pour Code-Golf . En général, et malgré l'exception pour [Code-Golf], le débordement de la pile n'est pas un lieu de concours.