简介

我们想要在一个字符串S中找到一个子串P（称为模式串），如果找到就返回该匹配串在S中起始位置。此时可以使用KMP算法（字母为三个提出者的姓名首字母）
传统的回溯法可能是这样的：在逐位检查匹配字符串P和S的过程中，如果发现当前字符S[i]与P[i]不匹配，那么从P[i-1]开始向前找S[i]，如果找到了P[j]==S[i]，那么从P[j]和S[i]向前遍历两字符串观察对应字符是否相等；否则就从P[0]开始重新和S[i]匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 代码未完成
n=S.length
m=P.length
for i in range(n):
    for j in range(j):
        if S[i] != P[j]:
            k=j-1
            while():
            for k in range(j):
                if S[i] == P[j-k]:
                    l=i-1
                    o=j-k-1
                    while(l >= 0 and o >= 0 and S[l] == P[o]):
                        l-=1
                        o-=1
                    if o < 0:

流程和实现