- 技术博客
- 28.实现strStr（） kmp算法
class Solution:
def strStr(self
, haystack
: str, needle
: str) -> int:
if not needle
: return 0
n
=len(haystack
);m
=len(needle
)
haystack
=' '+haystack
needle
=' '+needle
nt
=[0]*(m
+1)
j
=0
for i
in range(2,m
+1):
while j
and needle
[i
]!=needle
[j
+1]: j
=nt
[j
]
if needle
[i
]==needle
[j
+1]:j
+=1
nt
[i
]=j
j
=0
for i
in range(1,n
+1):
while j
and haystack
[i
]!=needle
[j
+1]:j
=nt
[j
]
if haystack
[i
]==needle
[j
+1]:j
+=1
if j
==m
: return i
-m
return -1
