今天数据结构课上的我好迷啊，如果以后可以带电脑上课就好了。今天上午两节课基本啥也没学，我佛了。
开始学习字符串匹配的KMP算法。
囤几个菊苣链接：
https://haihongblog.com/archives/911.html      （总结较好）
https://blog.csdn.net/v_july_v/article/details/7041827     （巨详细，只看了一半）
最开始的箬蒻版本，直接利用前缀后缀的最长长度表 
int n,m;
int nex[MAXN];//最长长度表
char a[MAXN],b[MAXN];
void gn()
{
    nex[1]=0;//
    int j=0;
    for(int i=2;i<=m;i++)//b字符自我匹配
    {
        //如果前一个字符的最长前缀后一个字符与i字符相同，则该字符最长长度即为j加一
        while(j>0&&b[j+1]!=b[i]) j=nex[j];
        if(b[j+1]==b[i]) j++;
        nex[i]=j;
    }
}
int kmp()
{
    int j=0;
    for(int i=1;i<=n;i++)//a,b,进行匹配，遍历a，同时不断移动b
    {
        //如果j字符的后一个字符匹配失败，此时已知j及以前的字符已经匹配成功
        //则退到j字符的最长前缀尾部再次进行比较，直到j退回空串情况或者匹配成功
        while(j>0&&b[j+1]!=a[i]) j=nex[j];
        if(b[j+1]==a[i]) j++;
        if(j==m)//子串匹配成功
            return i-m+1;//
    }
    return -1;
}
还有将最长长度表后移之后作为nex表，此时每个位置存的为前一个位置的最长长度，将i延伸到等于num2，方便求循环节
int s[1000010], p[10010];
int nex[10010];
int num1, num2;
void getnext()
{
    int i = 0, j = -1;
    nex[0] = -1;
    while(i != num2)
    {
        //(全部不相等从新匹配 || 相等继续下次匹配)
        if(j == -1 || p[i] == p[j])
            nex[++i] = ++j;
        else
            j = nex[j];
    }
}
优化之后的版本，此时nex不再是单纯的最长相同前后缀 
int s[1000010], p[10010];
int nex[10010];
int num1, num2;
void getnext()
{
    int i = 0, j = -1;
    nex[0] = -1;
    while(i != num2)
    {
        //(全部不相等从新匹配 || 相等继续下次匹配)
        if(j == -1 || p[i] == p[j])
        {
            ++i, ++j;
            if(p[i] != p[j])
                nex[i] = j;
            else//p[i]不能等于p[nex[i]],否则即使移动了也是无效移动
                nex[i] = nex[j];
        }
        else
            j = nex[j];
    }
}
int KMP()
{
    int i = 0, j = 0;
    while(i != num1 && j != num2)
    {
        //(全部不相等从新匹配 || 相等继续下次匹配)
        if(j==-1||s[i] == p[j])
            ++i, ++j;
        else
            j = nex[j];
        //如果j != -1，且当前字符匹配失败则令 i 不变，j = next[j]
    }
    if(j == num2)
        return i - j + 1;
    else
        return -1;
}
感觉后两种更好理解一点，要求最长前后缀用优化前，要用KMP就用优化后。

  • Cyclic Nacklace （KMP，循环节）

VJ链接：https://vjudge.net/contest/319836#problem/F
题意：给一个字符串，求最少补多少字符可以把他变成循环字符
一开始直接加减WA掉了，看了别人的题解才明白，，理解还是不够呀
比如如果现在的循环节为
图（理解）很重要）
这时候前面都是匹配的，那么循环节为strlen(s)-nex[strlen(s)]，需要添加的为 循环节 -nex[strlen(s)]%循环节
怎么也想不通的式子，一画图就非常清楚了，我太菜了哭）
int bu=m-nex[m];
if(m!=bu&&m%bu==0) printf("0\n");
else printf("%d\n",bu-nex[m]%bu);

  • Simpsons’ Hidden Talents （小坑）

VJ链接：https://vjudge.net/contest/319836#problem/G
求前一个字符串的前缀和后一个字符串的后缀最长相等长度，一开始直接将a,b相连然后求next，输出next [num1+num2]与num1,num2（两段字符串长度）的较小值
WA掉是因为，两字符串连接后可能在交界处形成循环节，例如：aabaa，baaba。
简单判断较小值行不通，这时就要根据next数组进一步向前推。（只贴核心几行叭，反正前面也是板子） 
int ans=nex[num2];
while(ans>num1||ans>num2-num1)
    ans=nex[ans];

  • Milking Grid （二维，思维）

VJ链接：https://vjudge.net/problem/POJ-2185
思路：没思路。
能想到是二维KMP可是我，不会写，看了题解才明白，这里虽然求的是二维的最小重复矩阵，但是行列互不影响，对行求一次nex，对列求一次nex，将行，列的最小循环节相乘即可。
解决这道题的关键是意识到二维矩阵的循环实际上在2个维度上是独立的，可以分别计算。
int j=-1,i=0;
        nex[0]=-1;
        while(i!=m)//将每一列看为一个字符元祖
        {
            if(j==-1||isR(i,j))
                nex[++i]=++j;
            else
                j=nex[j];
        }
        int ans=m-nex[m];//压缩之后的矩阵的最小循环节
        j=-1;i=0;
        while(i!=n)//每行看为一个字符元祖
        {
            if(j==-1||isC(i,j))
                nex[++i]=++j;
            else
                j=nex[j];
        }
        ans*=(n-nex[n]);