Questions sur les séquences de symboles, leurs ensembles et leurs propriétés ainsi que leurs utilisations.
J'essaie d'écrire un correcteur orthographique qui devrait fonctionner avec un dictionnaire assez volumineux. Je souhaite vraiment un moyen efficace d'indexer les données de mon dictionnaire en utilisant une distance de Damerau-Levenshtein pour déterminer les mots les plus proches du mot mal...
Supposons que et b 1 b 2 … b n sont deux chaînes de même longueur. Une anagrammation de deux chaînes est une cartographie bijective p : [ 1 … n ] → [ 1 … n ] telle que a i = b p ( i ) pour chaque i .une1une2… Unna1a2…ana_1a_2\ldots a_nb1b2… Bnb1b2…bnb_1b_2\ldots b_np : [ 1 … n ] → [ 1 … n...
Je recherche une structure de données qui stocke un ensemble de chaînes sur un jeu de caractères , capable d'effectuer les opérations suivantes. On note en tant que structure de données stockant l'ensemble des chaînes .D ( S ) SΣΣ\SigmaD (S)D(S)\mathcal{D}(S)SSS Add-Prefix-Seton : étant donné un...
Énoncé informel du problème: Étant donné une chaîne, par exemple , nous voulons colorer certaines lettres rouges et certaines lettres bleues (et certaines pas du tout), de sorte que la lecture des lettres rouges de gauche à droite donne le même résultat que la lecture seules les lettres...
Je recherche une structure de données qui prend en charge des recherches approximatives efficaces de clés (par exemple, la distance de Levenshtein pour les chaînes), renvoyant la correspondance la plus proche possible pour la clé d'entrée. La structure de données la mieux adaptée que j'ai trouvée...
Je suis curieux de savoir comment on pourrait compresser de manière très compacte le domaine d'un nom d'hôte IDN arbitraire (tel que défini par RFC5890 ) et je pense que cela pourrait devenir un défi intéressant. Un hôte ou un nom de domaine Unicode (U-label) se compose d'une chaîne de caractères...
Soit un ensemble fini de caractères de taille fixe. Soit une chaîne sur . Nous disons qu'une sous-chaîne non vide of est une répétition if pour une chaîne .ΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaβ=γγβ=γγ\beta = \gamma \gammaγγ\gamma Maintenant, ma question est de savoir si ce qui suit vaut: Pour...
Je m'intéresse à la question du temps d'exécution asymptotique de l'algorithme d'Ukkonen , peut-être l'algorithme le plus populaire pour construire des arbres de suffixes en temps linéaire (?). Voici une citation du livre "Algorithmes sur les chaînes, les arbres et les séquences" de Dan Gusfield...
J'ai travaillé sur le problème suivant de ce livre . Un certain langage de traitement de chaîne offre une opération primitive qui divise une chaîne en deux parties. Comme cette opération implique la copie de la chaîne d'origine, il faut n unités de temps pour une chaîne de longueur n, quel que soit...
Étant donné deux chaînes, comment pouvez-vous vérifier si elles sont une permutation l'une de l'autre en utilisant l'espace O (1)? La modification des chaînes n'est en aucun cas autorisée. Remarque: espace O (1) par rapport à la longueur de la chaîne ET à la taille de
La distance d'édition entre les listes Levenshtein-Distance est un problème bien étudié. Mais je ne trouve pas grand-chose sur les améliorations possibles s'il est connu qu'aucun élément ne se produit plus d'une fois dans chaque liste . Supposons également que les éléments soient comparables /...
On nous donne un tableau avec tous a [ i ] > 0 .a [ 1 … n ]a[1…n]a[1 \ldots n]a [ i ] > 0a[i]>0a[i]>0 Maintenant, nous devons trouver combien de sommes distinctes peuvent être formées à partir de ses sous-réseaux (où un sous-réseau est une plage contiguë du tableau, c'est-à-dire pour...
Lors d'une interview pour un poste de développeur Java, on m'a demandé ce qui suit: Écrivez une fonction qui prend deux paramètres: une chaîne représentant un document texte et un entier indiquant le nombre d'articles à retourner. Implémentez la fonction de telle sorte qu'elle retourne une liste de...
Je travaille sur des algorithmes de recherche de chaînes qui prennent en charge la recherche de modèles multiples. J'ai trouvé deux algorithmes qui semblent être les candidats les plus forts en termes de temps d'exécution, à savoir Aho-Corasick et Rabin-Karp . Cependant, je n'ai pu trouver aucune...
Cette page sur l'algorithme de Knuth-Moriss-Pratt par rapport à Boyer-Moore décrit un cas possible où l'algorithme de Boyer-Moore souffre d'une petite distance de saut alors que KMP pourrait mieux fonctionner. Je cherche un bon exemple (texte, motif) qui peut clairement démontrer ce...
Étant donné deux symboles et , nous allons définir les -ème chaîne de Fibonacci comme suit:aa\text{a}bb\text{b}kkk F(k)=⎧⎩⎨baF(k−1)⋆F(k−2)if k=0if k=1elseF(k)={bif k=0aif k=1F(k−1)⋆F(k−2)else F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2)...
Je suis à la recherche d'un algorithme d'appariement rapide de chaînes k-mismatch. Étant donné une chaîne de motif P de longueur m et une chaîne de texte T de longueur n, j'ai besoin d'un algorithme rapide (temps linéaire) pour trouver toutes les positions où P correspond à une sous-chaîne de T...
Supposons que l'on nous donne une collection de chaînes, S 1 , … , S n . Je voudrais savoir si l'une de ces chaînes est une sous-chaîne d'une autre chaîne de la collection. En d'autres termes, j'aimerais un algorithme pour la tâche suivante:nnnS1,…,SnS1,…,SnS_1,\dots,S_n Entrée:...
J'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...
Existe-t-il un algorithme à temps linéaire pour vérifier qu'une séquence de caractères est une concaténation de palindromes? La seule chose qui me vient à l'esprit est la solution naïve: 1. k = 1 2. Split string into k substrings (all possibilities) and check 3. k++ 4. repeat Remarque: la réponse...