Как построить массив LPS в алгоритме KMP с использованием Z-алгоритма - PullRequest
Новая
       45

Как построить массив LPS в алгоритме KMP с использованием Z-алгоритма

0 голосов
/ 25 сентября 2019

Я пытаюсь построить массив LPS для KMP, используя массив Z, полученный из алгоритма Z.Учитывая строку T и соответствующий массив Z z: 

T  = A T T C A C T A T T C G G C T A T
z  = 0 0 0 0 1 0 0 4 0 0 0 0 0 0 0 2 0
LPS= 0 0 0 0 1 0 0 0 0 0 4 0 0 0 0 0 2 (Want this LPS array)

Я спроектировал этот псевдокод (который выдает правильный массив LPS для указанной выше строки) 

ct = 1
for i to length of T
if z[i] != 0 {
    LPS[i + z[i] - ct++] = z[i]
} else {
    ct = 1;
}
//All other values get 0
end

Только для того, чтобы понять, что это не будет 't работает для строки: 

T = A A A A A A C A A A A A A A G
z = 0 5 4 3 2 1 0 6 6 5 4 3 2 1 0
LPS=0 1 2 3 4 5 0 1 2 3 4 5 6 6 0 (want this LPS array)

Приведенный выше алгоритм выдает 

LPS=0 1 2 3 4 5 1 1 2 3 4 5 6 0 0

Я пытался придумать, что нужно изменить в этом алгоритме, чтобы он правильно выдаетМассив LPS, использующий массив Z, но я застреваю.Буду признателен за любую помощь в этом.

...