String

Karp-Rabin

karp-rabin把字符串转化成数字的算法，一个字符串有n种字符构成，把每种字符对应为0～n-1中的一个数字，把字母换成对应的数字之后，对于固定长度的串，每个串都与一个唯一的n进制数对应。这样就可以hash了

ac自动机上的等价态：

等价态即用fail指针连接的点，在行走fail指针时匹配的字符数量并没有发生变化，因此这些点可以看成是相同的匹配状态。

通常有两种方法处理等价态，第一是互为等价态的点各自记录各自的信息。匹配的时候需要遍历所有等价态以判断是否匹配成功。next指针可能为空，需要匹配时进行判断是否需要走fail指针。

第二是所有等价态中的点记录本身以及所有比它浅的点的信息总和（匹配成功的单词总数），匹配时不需要走等价态以判断匹配成功与否。next指针不为空，直接指向本应通过fail指针寻找到的那个状态。

ac自动机与矩阵：

在ac自动机上，每一个从根出发并在自动机上行走的任意长度的路径都代表了一个字符串。

把ac自动机看成一个有向图的话我们可以提取它的邻接矩阵（可达矩阵），matrix[i][j]表示i和j是否相邻。

这个矩阵的n次幂matrix^n[i][j]表示从i恰好走n步到达j的路径有几条。

那可达矩阵对等价态是怎么处理的呢？如果考虑等价态，一个状态的可到达状态实在是太多了。因此我们这里认为的可达只是用地二中方法处理等价态时，next指针直接指向的被认为可达。