Предисловие: Мой вопрос в основном связан с алгоритмами, поэтому, даже если вы не знакомы с суффиксами и массивами LCP, вы, вероятно, сможете мне помочь.
В этой статье описывается, как эффективно использовать массивы суффиксов и LCP для сопоставления строковых шаблонов.
Я понял работу SA и LCP и то, как можно улучшить время выполнения алгоритма с O(P*log(N))
(где P
— длина шаблона, а N
— длина строки) до O(P+log(N))
(благодаря ответу Криса Элмаа здесь и ответ jogojapans здесь).
Я пытался пройти алгоритм на рисунке 4, который объясняет использование LLcp
и RLcp
. Но у меня проблемы с пониманием того, как это работает.
Алгоритм (взято из источника):
Объяснение используемых имен переменных:
lcp(v,w) : Length of the longest common prefix of v and w
W = w0..wP-1 : pattern of length P
A = a0..aN-1 : the text (length N)
Pos[0..N-1] : suffix array
L_W : index (in A) of first occurrence of the matched pattern
M : middle index of current substring
L : lower bound
R : upper bound
Lcp : array of size N-2 such that Lcp[M] = lcp(A_Pos[L_M], A_pos[M]) where L_M is the lower bound of the unique interval with M in the middle
Rcp : array of size N-2 such that Rcp[M] = lcp(A_Pos[R_M], A_pos[M]) where R_M is the upper bound of the unique interval with M in the middle
Теперь я хочу попробовать алгоритм, используя следующий пример (частично взятый из здесь):
SA | LCP | Suffix entry
-----------------------
5 | N/A | a
3 | 1 | ana
1 | 3 | anana
0 | 0 | banana
4 | 0 | na
2 | 2 | nana
A = "banana" ; N = 6
W = "ban" ; P = 3
Я хочу попытаться сопоставить строку, скажем, ban
, и ожидаю, что алгоритм вернет 0 как L_W
.
Вот как я бы прошёл алгоритм:
l = lcp("a", "ban") = 0
r = lcp("nana", "ban") = 0
if 0 = 3 or 'b' =< 'a' then // which is NOT the case for both conditions
L_W = 0
else if 0 < 3 or 'b' =< 'n' then // which is the case for both conditions
L_W = 6 // which means 'not found'
...
...
Я чувствую, что мне чего-то не хватает, но я не могу понять, что. Также мне интересно, как можно использовать предварительно вычисленный массив LCP вместо вызова lcp(v,w)
.
lcp(v, w)
самостоятельно, вы не можете вывести это из предварительно вычисленных массивов - любое lcp, включающее входную строку, потребует времени. Вот откуда взялась буква P вP + logN
. Насчетstep through algorithm
- это интересно. Я посмотрю это один день. - person Erti-Chris Eelmaa   schedule 11.02.2015'a' <= 'a'
, который оценивается как истина. - person Erti-Chris Eelmaa   schedule 11.02.2015w1
, этоwl
сl=0
и, следовательно, первый символ в W (то естьwl = 'b'
) - person Paddre   schedule 12.02.2015