алгоритм z-функции

Question

Вот пример поиска z-функции:

Пусть s=«abacaba»(вводится)

z[0] = 0 — по определению
z[1] = 0 — ищем длину наидл. общего префикса у abacaba и bacaba:bacaba начинается с b,поэтому z[1]=0
z[2] = 1 — ищем ДНОП у abacaba и acaba
z[3] = 0 — ищем ДНОП у abacaba и caba
z[4] = 3 — ищем ДНОП у abacaba и aba;abacaba
z[5] = 0 — ищем ДНОП у abacaba и ba

z[6] = 1 — ищем ДНОП у abacaba и a где ДНОП-длина наибольшего общего префикса

z = input()
y=list(z)
k=0
for i in range(0,len(y)):
  for x in range(1,len(y)):
    x=0
    if y[i+x]==y[x]:
        k+=1
    x+=1
print(k)

Answer 1

def z(string, idx):
    if not idx : return 0
    i=0
    for a,b in zip(string, string[idx:]):
        if not a == b :
            break
        i+=1
    return i

for i in range(len('abacaba')) :
    print(z('abacaba', i))

# 0 0 1 0 3 0 1

БЛОГ НА HUSL

алгоритм z-функции

Ответы (1 шт):