Linear-time substring search via prefix function (lps) to avoid re-scanning.
Precompute the longest proper prefix that is also a suffix (lps) for the pattern; while scanning the text, fall back using lps instead of restarting.
Use when you need deterministic O(n+m) substring search without hashing or when building editors/search tools.
Build lps (prefix function), then scan text and reuse lps to avoid backtracking.
Use this pattern when use when you need deterministic o(n+m) substring search without hashing or when building editors/search tools.
def kmp_search(s, p):
# build lps
lps=[0]*len(p); k=0
for i in range(1,len(p)):
while k>0 and p[k]!=p[i]: k=lps[k-1]
if p[k]==p[i]: k+=1; lps[i]=k
# search
j=0; res=[]
for i,ch in enumerate(s):
while j>0 and p[j]!=ch: j=lps[j-1]
if p[j]==ch: j+=1
if j==len(p): res.append(i-j+1); j=lps[j-1]
return resCompute lps in O(m) and reuse during search.
def kmp_search(s, p):
# build lps
lps=[0]*len(p); k=0
for i in range(1,len(p)):
while k>0 and p[k]!=p[i]: k=lps[k-1]
if p[k]==p[i]: k+=1; lps[i]=k
# search
j=0; res=[]
for i,ch in enumerate(s):
while j>0 and p[j]!=ch: j=lps[j-1]
if p[j]==ch: j+=1
if j==len(p): res.append(i-j+1); j=lps[j-1]
return resBuild lps in O(m), scan text once.
lps array of size m.