DAWG后缀自动机

SAM好像和DAWG是等价的概念。

什么是endpos？

考虑图上那个子串aabbabd，ab出现了两次，如果下标从1开始，则两次的结束位置分别是3和6。集合{3,6}

什么是等价类？

以状态7为例，能到达状态7的所有路径就是一个等价类。比如图里的aabbab abbab bbab bab。

常用性质

等价类中最长的就是前缀，也叫longest(x)
以状态7的等价类为例，aabbab
abbab
bbab
bab
在bab处就断开了。没有后续的ab和b。当一个串断开了，就需要一个后缀连接。

后缀连接（重要）

还是以状态7为例，后缀ab是断开的后缀里最长的，所以要把后缀连接指向ab。

bit并行算法

NFA与DFA

NFA是非确定性的有限状态机，DFA是确定性的。NFA在遇到某种情况失败的时候需要回溯，DFA不需要。直接列举了所有的可能性，所以速度快但是废很多很多的空间。

举这个例子，假如我输入ac。第一次匹配a成功，第二次它可能先尝试ab，发现不对，回来ac。这就回溯了。
DFA的话就全都列出来，不会回溯。

Shift-or 和 shift and

对于模式ababa，当处理完输入ababab时，给出状态字中的每个比特的值

shift-and就是每次左移后，补1，然后和表里的元素与运算。
or就是每次左移补0，和表里的元素或运算。

cliford算法

不知道干啥的

比特操纵算法

统计二进制数中1的个数

8X8置换网络