string - 从给定的字符串数组中查找所有子字符串的算法

Question

我需要从给定的字符串数组中找到所有子字符串并将它们分组。

附加条件：

如果字符串 S1 包含字符串 S2，S1 包含 S3，S2 包含 S4 - 它们都应该在一个组中。

例子：

给定数组： Hello, Hello John, Hi, Hi Bob, Hell, Hi all

结果输出：

第 1 组：你好，你好，约翰，地狱

第 2 组：嗨，嗨，鲍勃，大家好

Answer 1

• 在字符串数组上构建一个trie
• 对于每个数组条目，遍历 trie，如果当前节点标记了一个单词，则打印它（在与当前字符串相同的组下）。做一些簿记以避免多次打印同一个单词。

O(|w1| + ... + |wn|)制造轮胎的时间复杂度是|wi|绳子的长度wi；所以它在字符串长度的总和中是线性的。空间复杂度受相同表达式的限制，但当有很多公共前缀时（实际上会发生这种情况），空间复杂度会低得多。

查询步骤的时间复杂度与字符串的长度呈线性关系——只需遍历字符串对应的分支即可。（也许你可以标记你一路上访问过的字符串——并因此作为当前字符串的前缀——这样你以后甚至不会遍历它们。首先访问更长的字符串有助于你带来时间复杂度再向下。）

这是一个帮助您入门的结构：

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

插入很容易。root您从存储零字符（代表空字符串）的非 NULL 开始。

插入：

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

其他程序非常相似。Trie 是一种非常优雅、易于实现且易于使用的数据结构。