基本数据结构——KMP

功能    判断一个字符串是否在另一个字符串里出现过

next 数组求法
        1.初始化nest[1]=j=0,假设next[1~i-1]已经求出,下面求解next[i]
        2.不断尝试扩展匹配长度j,如果扩展失败(下一个字符不相等),
          令j=next[j],直至j为0(从头开始匹配)
        3.如果扩展成功,匹配长度j就增加1。next[i]的值就是j
        next[1]=0;
        for(int i = 2, j = 0; i <= m; i++)
        {        
            while(j && p[i] != p[j + 1])             
            j = ne[j];        
            if(p[i] == p[j + 1])             
                j++;        
            ne[i] = j;
        }

kmp
        for(int i=1,j=0;i<=m;i++)
        {        
            while(j>0&&p[i]!=p[j+1])
                    j=ne[j];
            if(p[i]==[j+1])
                    j++;
            if(j==n)
            {
                    j=ne[j];
                    cout<<i-n<<endl;//i-j为出现的位置的起始下标
            }
        }