所以我正在尝试用Python实现Knuth-Morris-Pratt算法，下面是我的实现：
def KMP(Pattern, Chars):
# compute the start position (number of characters)of the longest suffix that matches the prefix
# Then store prefix and the suffix into the list K, and then set the first element of K to be 0 and the second element to be 1
K = [] # K[n] store the value so that if the mismatch happens at n, it should move pattern Pattern K[n] characters ahead.
n = -1
K.append(n) #add the first element, and keep n = 0.
for k in range (1,len(Pattern) + 1):
# traverse all the elements in Pattern, calculate the corresponding value for each element.
while(n >=0 and Pattern[n] != Pattern[k - 1]): # if n = 1, if n >=1 and the current suffix does not match then try a shorter suffix
n = K[n]
n = n + 1 # if it matches, then the matching position should be one character ahead
K.append(n) #record the matching position for k
#match the string Chars with Pattern
m = 0
for i in range(0, len(Chars)): #traverse through the list one by one
while(m >= 0 and Pattern[m] != Chars[i]): # if they do not match then move Pattern forward with K[m] characters and restart the comparison
m = K[m]
m = m + 1 #if position m matches, then move forward with the next position
if m == len(Pattern): # if m is already the end of K (or Pattern), then a fully matched pattern is found. Continue the comparison by moving Pattern forward K[m] characters
print(i - m + 1, i)
m = K[m]
def main():
Pattern = "abcba"
letters = "abc"
Chars = print ( ''.join(random.choice(letters) for i in range(1000)) )
kmp(Pattern, Chars)
if __name__ == '__main__':
main()
当我试图为一个随机生成的字母列表运行此代码时，我会得到以下错误：
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-25-c7bc734e5e35> in <module>
1 if __name__ == '__main__':
----> 2 main()
<ipython-input-24-2c3de20f253f> in main()
3 letters = "abc"
4 Chars = print ( ''.join(random.choice(letters) for i in range(1000)) )
----> 5 KMP(Pattern, Chars)
<ipython-input-21-edf1808c23d4> in KMP(Pattern, Chars)
14 #match the string Chars with Pattern
15 m = 0
---> 16 for i in range(0, len(Chars)): #traverse through the list one by one
17 while(m >= 0 and Pattern[m] != Chars[i]): # if they do not match then move Pattern forward with K[m] characters and restart the comparison
18 m = K[m]
TypeError: object of type 'NoneType' has no len()
我真的不确定我做错了什么，任何帮助都将不胜感激
我更换后
Chars = print ( ''.join(random.choice(letters) for i in range(1000)) )
通过
Chars = ''.join(random.choice(letters) for i in range(1000))
它对我有效。