思路：

字符串s：aba   p：ababa(字符串下标从1开始)
next[i]存放的p[i]元素为结尾的后缀长度，这个后缀范围是 i - j + 1 ~ i,并且后缀与前缀相同，
前缀范围：1~j。例如next[5] = 3. 此时i = 5, j = 3后缀是3~5的“aba”，前缀是1~3的“aba”。
为什么构造这样的数组呢？
比如当验证的时候，aba在p数组前三个字符“aba”中验证完毕之后，暴力思路是把重头开始遍历s数组。
而有了next，跳回到前缀字串尾部，因此前缀字串和后缀字串相同，后缀字串又存在p数组中，因此前缀字串肯定也存在。这样就减少了不必要的步骤。
构造next执行过程：
while (j && s[i] != s[j + 1]) j = ne[j];
    if (s[i] == s[j + 1]) j ++ ;
    ne[i] = j;
有这样的字符串：s:ababc (j =0 i = 1)
 next[2] = 0, j=0 i=2 -> next[3] = 1,j=1,i=3 -> next[4] = 2,j=2,i=4 -> next[5]
 此时j=2指向b, j + 1 = 3指向a != c。j就需要向前回溯J= next[j] = 0;因为在前两个字符“ab”中，没有前缀符合next的成立条件了。
 所以next[5] = 0.表示p中在“c”前面找不到以“c”为结尾的子字符串。

算法1

$O(m+n)$

参考文献

基础课

C++ 代码

#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
char s[N], p[M];int ne[N];
int main()
{
    cin.tie(0);
    int n; cin >> n;
        cin >> s + 1;
    int m; cin >> m;
        cin >> p + 1;
    /*求next数组*/
    for(int i = 2, j = 0; i <= n; ++i)
    {
        while(j && s[i] != s[j + 1])j = ne[j];
        if(s[i] == s[j + 1])j++;
        ne[i] = j;
    }
   // for(int i = 1; i <= m; ++i)cout <<ne[i] << " ";
    /*字符串匹配*/
    for(int i = 1, j = 0; i <= m; ++i)
    {
        while(j && p[i] != s[j + 1])j = ne[j];
        if(p[i] == s[j + 1])j++;
        /*如果存在字串使得s在p里存在*/
        if(j == n)
        {

            cout << i - j<<" " ;
            j = ne[j];
        }
    }
    return 0;
}