Algorithmus zu finden alle Teilstrings aus dem gegebenen Array von String

Question

Ich brauche alle Teilstrings aus dem gegebenen Array von Strings und gruppieren sie zu finden.

Zusätzliche Bedingung:

Wenn String S1 String S2 enthält, S1 enthält S3, S2 enthält S4 - alle sie in einer Gruppe sein sollte.

Beispiel:

Gegeben Array: Hallo, Hallo John, Hallo, Hallo Bob, Hölle, Hallo alle

Ergebnisausgabe:

Gruppe 1: Hallo, Hallo John, Hölle

Gruppe 2: Hallo, Hallo Bob, Hallo zusammen

Answer 1

• baut ein trie auf dem Array von Strings
• Für jeden Array-Eintrag, zu Fuß die Trie und wenn der aktuelle Knoten ein Wort markiert, drucken Sie es (unter der gleichen Gruppe wie der aktuellen String). Führen Sie eine Buchhaltung durch, um zu vermeiden, dass das gleiche Wort mehrmals gedruckt wird.

Zeitkomplexität, die Reifen zu bauen ist O(|w1| + ... + |wn|) wo |wi| die Länge der Zeichenfolge ist wi; also ist es linear in der Summe der Längen der Saiten. Die Raumkomplexität wird durch denselben Ausdruck begrenzt, ist aber viel niedriger, wenn viele gemeinsame Präfixe vorhanden sind (was in der Praxis der Fall ist).

Der Abfrageschritt hat Zeitkomplexität linear in der Länge der Saite --- nur den Zweig durchquert, die die Zeichenfolge entspricht. (Vielleicht können Sie Strings, die Sie auf dem Weg besucht haben, abmelden - und werden daher der aktuellen Zeichenfolge vorangestellt - so dass Sie sie später nicht einmal durchqueren. Der Besuch längerer Strings hilft Ihnen, die zeitliche Komplexität zu erhöhen . weiter unten)

Hier ist eine Struktur, um loszulegen:

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) 
} 

Einfügen einfach. Sie beginnen mit Nicht-NULL root, die Nullzeichen speichert (die leere Zeichenfolge darstellt).

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; 
} 

Die anderen Verfahren sind sehr ähnlich. Trie ist eine sehr elegante, einfach zu implementierende und einfach zu bedienende Datenstruktur.