时间复杂度：
O(n)

算法模板：

#include <iostream>
using namespace std;
const int N = 10010,M = 100010;

int n , m;
char p[N],s[M];// s为长字符串，p为需要查找的字符串
int ne[N];//next数组

int main(){
    cin >> n ;
    for(int i = 1 ; i <= n ; i++) cin >> p[i];//从下标1开始存储
    cin >> m;
    for(int i = 1 ; i <= m ; i++) cin >> s[i];//从下标1开始存储

    //求next的过程
    for(int i = 2,j = 0 ; i <= n ; i++){
        while(j && p[i]!=p[j+1]) j = ne[j];//当前元素与上一位元素的next数组下一位不同，再深入上一位next数组的next数组
        if(p[i] == p[j+1]) j++;//当前元素与上一位元素的next数组下一位相同，直接下移一位即当前元素的next
        ne[i] = j;
    }

    //kmp匹配过程
    for(int i = 1,j = 0 ; i <=m ; i++){
        while(j && s[i]!=p[j+1]) j=ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n){
            printf("%d ",i-n);
            j=ne[j];
        }
    }

    return 0 ;
}

next数组示例：