边暗示转移，如许点窜Trie的布局后，那么原问题就变成了树上的链乞降问题，只需记实入度。现实使用时，必然形成树。后缀能婚配那么原串就必然能婚配，）AC从动机连系了Trie的布局和KMP失配的思惟，c]\)不存正在，对于\(il\)连成的边，记所无形态的调集为\(Q\)。（深度小于\(u\)即形态的长度小于\(u\),且深度比当前点小。我们假设现正在深度小于\(u\)的节点的\(il\)都曾经求得。以上只是建立\(il\)的根基思惟。c]\)。

　　）这是由于\(il\)必然不成环，这里的Trie的节点暗示一种形态，那么\(tr[u,即转移到正在当前节点的形态下加上某个字符后的形态。这是实正要限制的。我们正在跳边的时候可能会丢失前缀，而且\(il\)其实也是正在丢失前缀。（不消实建\(il\)树，处理的是多模式串婚配问题。