kmp的关键之处还是在Next数组上
Next存的是前缀和后缀相等的长度
基础的模板题就不上啦，来几个应用题目~~~
POJ-2185
给出一个大矩阵，求最小覆盖矩阵，大矩阵可由这个小矩阵拼成。（就如同拼磁砖，允许最后有残缺）
emmm~~二维滴，本来想
KMP的next求出每行的最小循环子串长度,然后求这些长度的公倍数，作为宽（若大于col，则为col）。
然后用KMP的next求出每列的最小循环子串长度，然后求出这些长度的公倍数，作为长（若大于row，则为row）。
虽然我最后也过了，but 有反例的
2 8
ABCDEFAB
AAAABAAA
答案是12 ，所以很多人可能会想对于单行我们不一定要选最短循环节，所以需要把所有的循环节求出，取lcm最小的
当然没问题啦
but 有更骚的操作哦，那就是直接用kmp的Next数组，在比较的时候不是比较单个字符而是比较两行/两列
真实是个好题~（奈何数据太弱，错误解法也能AC）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;const int maxn = 1e4 + 10;
int n,m,t,k,ans;
char s[maxn][100];
int Next[maxn];bool cmp(int x,int y,int f)
{if(f){for(int i = 0;i < m; ++i) ///比较行if(s[x][i] != s[y][i]) return 0;return 1;}for(int i = 0;i < ans; ++i) ///比较列if(s[i][x] != s[i][y]) return 0;return 1;
}void getNext(int x)
{int i = 0,j = Next[0] = -1,k;if(!x) k = m;else k = n;while(i < k){if(j == -1 || cmp(i,j,x))Next[++i] = ++j;else j = Next[j];}
}int main()
{scanf("%d%d",&n,&m);for(int i = 0;i < n; ++i)scanf("%s",s[i]);getNext(1);ans = n - Next[n];getNext(0);ans *= (m - Next[m]);printf("%d\n",ans);return 0;
}