Algorithme pour trouver toutes les sous-chaînes du tableau donné

Question

J'ai besoin de trouver toutes les sous-chaînes du tableau de chaînes donné et de les grouper.

Condition supplémentaire:

Si la chaîne S1 contient la chaîne S2, S1 contient S3, S2 contient S4 - tous devraient être dans un groupe.

Exemple:

tableau donné: Bonjour, Bonjour John, Salut, Salut Bob, Enfer, Salut à tous

sortie Résultat:

Groupe 1: Bonjour, Bonjour John, Hell

Groupe 2: Salut, Salut Bob, Salut Tous

Answer 1

• Construire une trie sur le tableau de chaînes
• Pour chaque entrée de gamme, la marche et si le Trie nœud actuel marque un mot, l'imprimer (sous le même groupe que la chaîne en cours). Faites de la comptabilité pour éviter d'imprimer le même mot plusieurs fois.

complexité du temps pour construire le pneu est O(|w1| + ... + |wn|) où |wi| est la longueur de la chaîne wi; donc c'est linéaire dans la somme des longueurs des cordes. La complexité de l'espace est limitée par la même expression mais est beaucoup plus faible quand il y a beaucoup de préfixes communs (ce qui arrive en pratique).

L'étape de requête a une complexité de temps linéaire dans la longueur de la chaîne --- juste traverser la branche qui correspond à la chaîne. (Peut-être que vous pouvez marquer les chaînes que vous avez visitées le long du chemin --- et sont donc préfixés de la chaîne en cours --- de sorte que vous ne les traverserez même pas plus tard. . plus bas)

Voici une struct pour vous lancer:

typedef struct node_t_ node_t; 
struct node_t_ { 
    node_t c *children[ALPHABET_SIZE]; 
    char kIsLeaf; // set to 1 if represents a word 
    char ch; // character stored in the leaf (redundant) 
} 

est facile Insertion. Vous commencez par root non nul qui stocke zéro caractère (représente la chaîne vide).

Insertion:

void insert(const char* str) { 
    node_t* current = root; 
    while (*str != '\0') { 
     if (current->children[*str] == NULL) { 
      create new node; 
     } 
     current = current->children[*str++]; 
    } 
    current->kIsLeaf = 1; 
} 

Les autres procédures sont très similaires. Trie est une structure de données très élégante, simple à mettre en œuvre et facile à utiliser.