我不太了解在字符串匹配中使用的实际算法。
我想知道为什么似乎有更多的关注后缀尝试字符串匹配，而不是前缀尝试。我们可以不使用前缀尝试子字符串匹配吗?换句话说，后缀尝试比前缀尝试有什么优势?
。
认真。后缀尝试允许您从字符串的开头遍历。
我认为这里出现的一些混淆是因为术语"后缀三叉树"不仅仅意味着"包含后缀的三叉树"。相反，后缀树通常表示"包含给定字符串的所有后缀的前缀树"。这与"前缀树"形成对比，后者通常存储字符串的任意集合，而不是给定字符串的所有前缀。
后缀树有用的原因是以下事实，有时称为弦学的基本定理:
字符串x是字符串w的子字符串当且仅当x是w的后缀的前缀
例如，"irate"是"pirates"的子字符串，因为它是后缀"irates"的前缀。
这就是为什么后缀尝试在子字符串搜索中如此出色。假设你想知道x是否是w的子串，进一步假设，你得到了w的后缀树，然后你可以从根结点向下遍历后缀树看看你是否可以读取x而不会从树上掉下来。如果是，x是w的某个后缀的前缀，因此x是w的子字符串。如果不是，x不是w的任何后缀的前缀，因此x不是w的子字符串。
正如@Ed Staub的回答所示，你可以很容易地做到这一点，通过使用一个树来存储w的所有前缀，然后检查x是否是w的任何前缀的后缀。但在实践中，更容易考虑将所有后缀保存在一个前缀树中，所以这就是我们所做的。