Tôi đang xem mã giả được đưa ra trong hình 3 của bài báo gốc giới thiệu các mảng hậu tố "SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES".Errata trong tài liệu gốc trên các mảng hậu tố?
Tôi không thể tìm ra logic cho các dòng 4 và 5 (lập chỉ mục từ 0). Các dòng đọc:
else if r < P hoặc w r ≤ một Pos [N-1] + rsau đó
L W ← N
W
là mẫu có độ dài 'P' mà chúng tôi đang tìm kiếm và r
là lcp(A[pos[N-1]:], W)
. Vấn đề là trong hầu hết các trường hợp, lcp
này sẽ nhỏ hơn độ dài 'W'. Điều này có nghĩa là để xử lý các trường hợp (tôi nghĩ) rằng mô hình là lexicographically lớn hơn so với hậu tố lexicographically lớn nhất trong mảng, nhưng nó không kiểm tra này cả. Dòng 2 & 3, mặt khác, trong đó kiểm tra nếu W
là ít hơn so với hậu tố tự từ điển nhỏ dường như có ý nghĩa hoàn hảo
nếu l = P hoặc w l ≤ một Pos [0] + lsau đó
L W ← 0
Tôi tin rằng các dòng gốc nên đọc cái gì đó như:
else if r < P và w r> một Pos [N-1 ] + rrồi
L W ← N
Cách duy nhất mà W
có thể lớn hơn A[pos[N-1]:]
là nếu nó có một lcp
ngắn hơn độ dài của mô hình (nếu không, tất cả các W
trận đấu và do đó W
không thể lớn hơn, chỉ nhỏ hơn hoặc bằng điều mà chúng tôi đang chia sẻ số lcp
) VÀ nếu ký tự sau lcp
lớn hơn trong W
so với số A[pos[N-1]]
. Điều này có vẻ hợp lý không? Đây có phải là lỗi trong bài báo gốc không? Nếu không, ai đó có thể vui lòng giải thích cho tôi cách tôi hiểu sai mã gốc không?