O(n+m)
在s[m]中寻找子串p[n]

int ne[N];
char p[N], s[N];

cin >> n >> p + 1 >> m >> s + 1;

for (int i = 2, j = 0; i <= n; i++) //求next数组
{
    while (j && p[i] != p[j + 1])
    {
        j = ne[j];
    }
    if (p[i] == p[j + 1])
    {
        j++;
    }
    ne[i] = j;
}

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)//匹配成功后的操作
    {
        cout << i - j + 1 << ' ';//i-j+1为p在s中出现的起始下标
        j = ne[j];//继续向后匹配
    }
}