c# - 哪些算法用于搜索单词中的子词？

Question

我知道，也许这个问题很愚蠢，但我被困住了，我需要真正的帮助。我需要在我的项目中使用算法来找到所有以另一个开头的单词并返回所有单词的尾部。例如:查找所有以 dad

开头的单词

在字典中我们有:

dada，dadaism，daddled，daddling

结果:

a, aism, dled, dling

我有包含所有单词的字典，所以我只需要算法。有人建议我使用 patricia 算法，但我找不到任何 C# 示例。我的字典很大，所以我需要找到也非常快的算法。

---

更多信息:

字典排序。

Answer 1

如何进行这项工作将取决于您的词典是如何排列的。如果它是一个排序的单词列表，那么您可以使用二进制搜索找到以“dad”开头的第一个单词，然后循环使用 StartsWith 和 Substring .即:

List<string> Words = LoadWords(); // however you load them
Words.Sort();

// Now, search for "dad" (or whatever)
string prefix = "dad";

int index = Words.BinarySearch(prefix);

// If the returned index is negative, the word wasn't found.
// The index is the one's compliment of the the place where it would be in the list.
if (index < 0)
{
    index = ~index;
}

for (int i = index; i < Count && Words[i].StartsWith(prefix))
{
    Console.WriteLine(Words[i].Substring(prefix.Length));
}

这应该很快。排序是加载后的一次性成本。如果按排序顺序存储字典，则可以完全消除它。二进制搜索是 O(log n)，其中 n 是字典中的单词数。

如果您的字典是无序的，那么您将不得不遍历所有单词，这会花费很多时间。

您的词典还有其他组织方式，这将大大减少它占用的空间，而且速度可能会更快。与创建排序列表相比，这些更复杂并且需要更多时间来构建。