匹配方式

三种情况：
长串的i位置与模板串的j位置进行比较：

1. if s[i] == p[j] -> i,j;
2. else if j && s[i] != p[j] -> i++, j = ne[j];
3. else i++;
4. 结束 j == m，匹配成功，输出i - m；

证明

要证明的是p串可以从j直接移动到next[j];那么i到next[j]之间的字符不会成功匹配吗？
不会的，因为如果在主串i2位置开始能够成功匹配，此时的i2在next[j]与i之间，就是说i2>next[j];p串中就会存在一个从
起始位置开始到i2的前缀等于后缀的长度，且该长度大于0-next[j],这就与next[j]的含义不符。所以不能出现这种情况

时间复杂度

构造一个i，最大为n；一个i-j，最大n
在上述三个分支中：

1. i++, j++;
2. j—;
3. i++;
   三种情况最大的活动范围为2n，那么时间复杂度为O(n);

next数组求法

用p数组自己与自己匹配；
比较j+1 与i 时假设之前的next[j]已经求出；
那么只要比较j = next[j]时的p[j+1],p[i]就行：
while(j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
p[i] = j;

时间复杂度

构造i，i - j
可知最大O(m);