Développement Java
  1. Développement Java
  3. Algorithme pour trouver l’union de plusieurs chaînes groupées par index de caractères
Intereting Posts
Que signifie ‘major.minor version 52.0’ non supporté et comment le corriger? Comment créer un bon modèle de formation NER dans OpenNLP? Bibliothèque Java pour mapper le code de statut HTTP à la description? Comment se connecter au serveur FTPS avec une connexion de données utilisant la même session TLS? Comment puis-je insérer un object JSON dans Postgres à l’aide de Java prepareStatement? Comment passer des arguments à un agent d’instrumentation Java? envoyer un e-mail et vérifier le statut Mauvais type sur la stack d’opérandes… en utilisant jdk 8, les lambda avec des classes internes anonymes échouent, pourquoi Est-il possible de créer un tableau primitif sans initialisation? Est-il possible de geler System.currentTimeMillis () pour le test Nom du package interdit: java Comment renvoyer un sous-ensemble d’une entité JPA appartenant à une autre entité? Procéder avec des arguments variables avec AspectJ Qui utilise le logiciel de filigrane? Apache PoolingHttpClientConnectionManager levant une exception d’état illégale

Algorithme pour trouver l’union de plusieurs chaînes groupées par index de caractères

J’ai essayé de trouver un moyen efficace de rechercher l’union des occurrences de caractères dans un ensemble de chaînes de fixed width groupées par index. Quelque chose comme ça; 

 s1 = "013965" s2 = "015935" s3 = "310012"

Il en résulte que chaque groupe de chiffres existe dans toutes les chaînes de l’index de caractères n: 

 out = "[03][1][350][90][631][52]"

J’ai pensé faire cela de la manière très naïve d’itérer chaque chaîne, chaque index, tout en stockant les chaînes intermédiaires dans un tableau, puis en parcourant ce tableau pour créer la valeur de sortie. Cependant, mon approche me semble être une méthode extrêmement inefficace et bien trop éloignée d’une solution asymptotiquement optimale.

Si le jeu de tous les caractères possibles est connu à l’avance, supposons que leur nombre est n , n n’étant pas trop élevé (par exemple, 10, si vous ne faites que des chiffres), vous pouvez le faire en créant m tableaux booléens de longueur n , m étant le nombre de positions ou de chiffres dans les chaînes d’entrée et n . La n-ième position dans le m-ième tableau sera true si le n-ième caractère est présent dans la m-ième position dans l’une des chaînes en entrée. False indiquera qu’aucun personnage de ce type n’était auparavant en position m.

Ensuite, vous pouvez parcourir chaque chaîne et, lorsque vous rencontrez le caractère n en position m vous définissez true à la n-ième position du m-ème tableau. À la fin, vous aurez des tableaux décrivant chacun le contenu du m-ème groupe. 

 pos[0] = {true, true, false, false, false, true, true, false, true, false} pos[1] = {true, false, false, false, false, false, false, false, false, false} pos[2] = {false, false, true, true, false, false, false, false, false, true}

Se traduit par 

 [0,1,5,6,8] [0] [2,3,9]

Comme toutes les structures sont des tableaux à access direct, il n’y a aucune recherche impliquée, tout access est en temps constant et il vous suffit de visiter chaque personnage une fois, sans comparaison. J’espère que cela t’aides.