// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度

// 求模式串的Next数组：
next[1] = 0;
// i与j+1进行配对, j从0开始

// j事实上代表的是公共前缀，i代表的是公共后缀
for (int i = 2, j = 0; i <= m; i ++ )
{
    // 当j不在起始位置且不匹配时,j回退到ne[j], 注意while中条件是不等于;
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}
/* 
   next数组存储前缀和后缀的最长公共字符串长度, 匹配不成功时将模式串的前缀移动到后缀的位置
   a b a b a b a b
   1 2 3 4 5 6 7 8
   next[1] = 0;
   next[2] = 0;
   next[3] = 1;
   next[4] = 2;
   next[5] = 3;
   next[6] = 4;
   next[7] = 5;
   nect[8] = 6;
*/

// 匹配
// 模式串匹配失败时, 每次向前移动的距离：已匹配的字符串长度 - 前缀和后缀的最长公共字符串长度
// 也即j每次将要回退的位置( 前缀最长公共字符串的最后一位 ) 与 当前位置的距离差
// j回退的距离也代表模式串的最长公共前缀移动到最长公共后缀的位置
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m) // 模式子串的长度
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}