参考了一些博客，如有侵权，请告知。内部资料，包不外传。定义后缀自动机（SAM）的结构包含两部分，有向无环单词图（DAWG）和parent树。SAM中的每个节点都同时存在于这两个结构中。以下假设我们是关于字符串\(s\)的SAM。DAWGDAWG是一个DAG。我们令起始结点为\(st\)，\(st\)在DAWG