UVA11019 Martix Matcher
题目描述：
给定一个\(n*m\)的文本串
问一个\(x*y\)的模式串出现的次数
AC自动机的奇妙使用
将\(x*y\)的模式串拆分成x个串，当x个串在同时被匹配时，认为原串被匹配
但是要区分匹配的行的差别，因此额外的附加一个二维数组\(cnt\)来表示匹配情况
记\(cnt(i,j)\)表示以\((i,j)\)为左上角的大小为\(x*y\)矩阵匹配了多少行。
将模式串拆成x个串，建成AC自动机
把文本串的n行放进去分别匹配，当枚举到文本串中的第i行第j个字符时，
如果匹配上了模式串中第k行，那么\(cnt(i - k, j - y + 1) +1\)
最后的答案即为\(\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} [cnt(i,j)==x]\)
复杂度O(\(T(n*m+x*y)\))
但是，本题很坑
1.模式串可能有相同的两行，尽管模式串行结尾的fail指针不会互指，但是这种情况下要用链表储存
2.每次清AC自动机不要整个全部清，会带来极大的复杂度
3.尽量不要以1作为下标，讨论将变得很复杂
4.哈希的常数更优
5.本题卡常，如果过不去，考虑哈希