题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式
第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串S。

输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围
1≤N≤10^5
1≤M≤10^6

样例

输入样例：
3
aba
5
ababa
输出样例：
0 2

算法1

暴力枚举

算法2

KMP

预处理数组
p[1,j] = p[i-j+1,i],i为终点。next[i]=j
下标从1开始

时间复杂度

O(n)

python 代码

if __name__ == "__main__":
    n = int(input())
    p = [0] + list(input())     #模板串
    m = int(input())
    s = [0] + list(input())     #模式串
    ne = [0]*100010

    #求ne[]数组
    j=0
    for i in range(2,n+1):      #ne[1]=0,所以i从2开始
        while j and p[i]!=p[j+1]:
            j=ne[j]
        if p[i]==p[j+1]:
            j+=1
        ne[i]=j

    #kmp匹配过程
    j=0
    for i in range(1,m+1):              #最多执行2m次，时间复杂度为O(2m)，即O(n)
        while j and s[i] != p[j+1]:     #如果j可以退，且下一个字符不匹配,j就往后退一步
            j=ne[j]                     #while循环内j最多-m次
        if s[i]==p[j+1]:
            j+=1                        #for循环内j最多+m次，
        if j==n:
            print(i-n,end=" ")
            j=ne[j]