Errata, sonek dizileri hakkındaki orijinal belgede mi?

Question

"SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES" sonek dizilerini tanıtan orijinal kağıdın şekil 3'ünde verilen sözde kodu inceliyorum.

Çizgiler 4 ve 5 için mantığı çözemiyorum (0'dan dizin oluşturma). hatlar okur:

başka

P r < halinde veya bir _{Pos [N-1] + 'r, daha sonra}
L _{W ≤ r ağırlık} ← N

W, aradığımız 'P' uzunluğunun desenidir ve r, lcp(A[pos[N-1]:], W)'dir. Sorun şu ki, hemen hemen tüm durumlarda, bu lcp, 'W' uzunluğundan daha az olacaktır. Bu koşul, olayı (bence) dizinin söz dizisindeki sözcükbilimsel olarak en büyük sonekten sözcükbilimsel olarak daha büyük olduğunu, ancak bunu hiçbir zaman test etmediğini düşünür. Çizgiler 2 & 3, sözlük sırasında küçük eki daha az mükemmel mantıklı görünmektedir, test W Diğer taraftan, ilgili

halinde L = P veya l _{ağırlık ≤ bir Pos [0] + l ardından
L W ← 0}

özgün çizgiler gibi bir şöyle olmalıdır inanıyoruz:

başka

P r < halinde ve _{W R}> bir _{Pos [N-1 ] + r}
L _W ← N

WA[pos[N-1]:] daha büyük olabilir tek yol desenin uzunluğunun (aksi halde, tüm W ile eşleşir ve böylece W büyük olamaz daha bir lcp kısa varsa olduğu, lcp'u paylaştığımız şeyle yalnızca daha az veya eşittir. VE lcp'dan sonraki karakter W'da A[pos[N-1]]'dan daha büyükse. Bu mantıklı geliyor mu? Bu, orijinal belgede bir hata mı? Değilse, birisi bana orijinal kodu nasıl yanlış yorumladığımı açıklayabilir mi?

Answer 1

Sanırım kağıdı doğru anlıyorsunuz ve aslında bir hatası var.

Aşağıdaki örneği ele alalım: A = banana, W = nana izin verin. Sonra A[pos[N-1]:] = nana. Algoritma LW = N'u ayarlar veya aslında N-1 ise başarısız olur.