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

问题描述：

我需要从给定的字符串数组中找到所有子字符串并对它们进行分组。从给定的字符串数组中找到所有子字符串的算法

附加条件：

如果字符串S1包含字符串S2，S1包含S3，S2包含S4 - 所有这些应该是在一组。

实施例：

鉴于阵列： 你好，你好，约翰，HI，您好鲍勃，地狱，大家

结果输出：

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

第2组：你好，鲍勃，你好全部

你在哪里有问题？ – Henry

在我目前的实现（蛮力）中，我面对N * N复杂性（这是预期的），这对于巨大的数组无效。 –

答

生成字符串数组
对于每个阵列条目上的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开始，它存储零个字符（表示空字符串）。

插入：

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是一个非常优雅，易于实现且易于使用的数据结构。

但是我们应该如何处理像“Hello world”，“world”这样的按键？他们也应该在一个组中，因为第一个字符串包含第二个字符串，但是在Trie中他们将处于不同的路径。 –

嗯...一个后缀树是一个很好的数据结构对于这样的问题... – blazs

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

相关推荐