Пытался сам разобраться в написании алгоритма Кнута-Морриса-Пратта на питоне и столкнулся с проблемой, обойти которую мне не по силам. Первая функция ищет префикс-функцию и в целом работает, а вторая собственно сам алгоритм. Проверить это дело я пытась последним куском кода.
def pref_suff(A):
P = [0]*len(A)
for i in range (1, len(A)):
j = P[i-1]
while j > 0 and A[i] != A[j]:
j = P[j-1]
if A[i]==A[j]:
j+=1
P[i]=j
return [P]
def kmp(A, B):
P = pref_suff(B)
j = 1
for i in range (len (A)):
while A[i]!=B[j] and j > 0:
j = P[j-1]
if A[i]==B[j]:
j+=1
if j==len(B):
return True
else:
if i == len(A)-len(B)+1:
return False
A = [1, 2, 3, 1, 2, 5, 1, 2, 3, 1, 2, 3, 1, 2, 4]
F = [1, 2, 3, 1, 2, 4]
c = kmp(A, F)
print (c)
И в итоге столкнулся с тем, что в алгоритме КМП переменна j определяется как list и я не могу уйти от цикла while потому что банально не могу сравнить её с нулём или найти B[j]. Надеюсь на вашу помощь.