week3_KMP

这个本来就会哈哈哈哈(脑子有坑)
B里是否存在A 典型的模式匹配 不好意思这道题在下也做过。
2013年小学期结课。个人赛大概第三或四题吧。
那时的我连筛素都不会。真是逝去的青春啊。
(但是为什么筛素都不会的时候就搞定了KMP啊啊啊)
说不清这是记性太好还是太坏。因为KMP算法本身我一点都记不起来。
就好像 清楚地记得哪一天走过哪个街道 记得天色和光线 唯独不记得在哪。
好在只要把我带过去，我就可以全都想起来。
看完题就想起来了，呵呵。
首先获取next数组；next[j]代表字符串对齐位；
bababbab
00123123
i是在原模式串的位置，j是对齐位
init:原模式串位于起点位0，j先对不上在-1
j=-1->i和j各移一位，next[1]=0,i=1,j=0;
j=0->0位和1位对不上了， j=next[0]=-1;
j=-1->i和j各移一位，next[2]=0,i=2,j=0;
j=0->0位和2位对上了，next[3]=1,i=3,j=1;
此后一路匹配至
j=3，next[5]=3,i=5,j=3;
但是->4位和6位对不上了，j=next[j]=next[3]=1
已知3-5和1-3妥妥对着的，那么显然1=3=5，直接看2是否等于6
那么显然s[1]!=s[5] 继续往前核对，j=next[1]=0
just so.

void getnext(char sub[],int next[],int len2)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<len2)
    {
        if (j==-1||sub[i]==sub[j])
            i++,j++,next[i]=j;
        else j=next[j];
    }
}

至于kmp是这样的：
拿着模式串和给定串去做对比
类似于寻找next的过程；
对上了就j++继续移；
对不上就把模式串平移到next位继续对；
都对上了j就等于len2了。

int kmp(char s[],char sub[],int len1,int len2,int next[])
{
    int i=0,j=0;
    while(i<len1)
    {
        if (j==-1||s[i]==sub[j])
            i++,j++;
        else j=next[j];
        if(j==n) cnt++;
    }
    else return -1;
}

选错编译器CE了一回。数组开小了RE了一回。下次多看一眼题。嗯