正如我在评论中指出的那样，前缀和后缀的情况被一般的子字符串情况（#2）所覆盖。根据定义，所有前缀和后缀也是子字符串。所以我们要解决的只是一般的子串问题。
由于您有一个静态字典，因此您可以相对轻松地将其预处理为快速查询子字符串的形式。您可以使用后缀树来做到这一点，但是构建和处理简单的排序平面数据向量要容易得多，所以这就是我将在此处描述的内容。
因此，最终目标是获得一个排序的子词列表，以便可以进行二进制搜索以找到匹配项。
首先，观察为了找到与查询片段匹配的最长子串，不必列出每个单词的所有可能的子串，而只需列出所有可能的后缀；这是因为所有子字符串都可以仅仅被认为是 suffixes 的前缀。（明白吗？第一次遇到它有点费解，但最后很简单，非常有用。）
因此，如果您生成每个字典单词的所有后缀，然后将它们全部排序，您就有足够的能力在任何字典单词中找到任何特定的子字符串：对后缀进行二进制搜索以找到下限 ( std::lower_bound) -以查询片段开头的第一个后缀。然后找到上限 ( std::upper_bound) - 这将是查询片段开头的最后一个后缀的后缀。[lower,upper[ 范围内的所有后缀都必须以查询片段开头，因此这些后缀最初来自的所有单词都包含查询片段。
现在，显然实际上拼出所有后缀会占用大量内存——但您不需要这样做。后缀可以被认为仅仅是一个词的索引——后缀开始的偏移量。因此，每个可能的后缀只需要一对整数：一个用于（原始）单词索引，一个用于该单词中后缀的索引。（您可以根据字典的大小巧妙地将这两个打包在一起，以节省更多空间。）
总而言之，您需要做的就是：
- 为所有单词生成一个包含所有单词-后缀索引对的数组。
- 根据它们作为后缀（不是数值）的语义对它们进行排序。我建议
std::stable_sort使用自定义比较器。这是最长的步骤，但可以离线完成一次，因为您的字典是静态的。
- 对于给定的查询片段，在已排序的后缀索引中找到下限和上限。此范围内的每个后缀对应一个匹配的子字符串（查询的长度，从单词索引处的单词的后缀索引开始）。请注意，某些单词可能匹配不止一次，并且匹配甚至可能重叠。
为了澄清，这里有一个由“臭鼬”和“奶酪”组成的字典的小例子。
“臭鼬”的后缀是“臭鼬”、“kunk”、“unk”、“nk”和“k”。用指数表示，它们是0, 1, 2, 3, 4。“cheese”的后缀是“cheese”、“heese”、“eese”、“ese”、“se”和“e”。指数为0, 1, 2, 3, 4, 5。
由于“skunk”是我们非常有限的虚构词典中的第一个词，我们将为其分配索引 0。“cheese”位于索引 1。所以最后的后缀是：0:0, 0:1, 0:2, 0:3, 0:4, 1:0, 1:1, 1:2, 1:3, 1:4, 1:5。
对这些后缀进行排序会产生以下后缀字典（我添加了实际对应的文本子字符串仅用于说明）：
0 | 0:0 | cheese
1 | 0:5 | e
2 | 0:2 | eese
3 | 0:3 | ese
4 | 0:1 | heese
5 | 1:4 | k
6 | 1:1 | kunk
7 | 1:3 | nk
8 | 0:4 | se
9 | 1:0 | skunk
10 | 1:2 | unk
考虑查询片段“e”。下限为 1，因为“e”是大于或等于查询“e”的第一个后缀。上限为 4，因为 4（“heese”）是第一个大于“e”的后缀。因此 1、2 和 3 处的后缀都以查询开头，因此它们来自的单词都包含作为子字符串的查询（在后缀索引处，用于查询的长度）。在这种情况下，所有这三个后缀都属于“奶酪”，具有不同的偏移量。
请注意，对于不是任何单词的子字符串的查询片段（例如本例中的“a”），没有匹配项；在这种情况下，下限和上限将相等。