آرایه‌ی پسوندی و LCP

همه‌ی پسوندهای رشته را مرتب می‌کند و برای هر دو پسوند همسایه طول بلندترین پیشوند مشترک را با روش کاسای در O(n) حساب می‌کند.

آرایه‌ی پسوندی محل شروع همه‌ی پسوندهای یک رشته است، مرتب بر اساس خود پسوندها. هر زیررشته پیشوندِ یک پسوند است؛ پس با جست‌وجوی دودویی روی آرایه‌ی پسوندی می‌شود هر الگو را در O(m log n) پیدا کرد.

ادامه‌ی توضیح ↓

زمان: O(n² log n) to sort here (O(n log n) with doubling), O(n) for LCP
حافظه: O(n)
CLRS، بخش ۳۲.۵

ورودی:

S="banana"خروجی PDF

banana؛ پسوندهای مرتب: a، ana، anana، banana، na، nana و LCP ها ۰، ۱، ۳، ۰، ۰، ۲.

def suffix_array(S):
n = len(S)
sa = sorted(range(n), key=lambda i: S[i:]) # the start positions, in the order of their suffixes
rows = [[sa[k], S[sa[k]:], "-"] for k in range(n)]
rank = [0] * n
for k in range(n):
rank[sa[k]] = k
# Kasai: going through the suffixes in text order, the common prefix shrinks by at most one each time.
h = 0
for i in range(n):
if rank[i] == 0:
h = 0
continue
j = sa[rank[i] - 1] # the suffix just before S[i:] in sorted order
while i + h < n and j + h < n and S[i + h] == S[j + h]:
h = h + 1
rows[rank[i]][2] = h
if h > 0:
h = h - 1
return sa

ناوردا: اگر پسوند i با همسایه‌اش h نویسه‌ی مشترک داشته باشد، پسوند i + 1 دست‌کم h − 1 نویسه با همسایه‌ی خودش مشترک دارد؛ پس h هیچ‌وقت بیش از یکی کم نمی‌شود.

شروع اجرا

012345

banana

h—

جدول هنوز خالی است.

متغیرهای محلی

S'banana'

نارنجی = در همین گام عوض شد

Call stack

suffix_array()خط 1

گام ۱ از ۶۴

توضیح

ایده

آرایه‌ی LCP

LCP[k] طول بلندترین پیشوند مشترک پسوند k ام و (k−1) ام (در ترتیب مرتب) است. بزرگ‌ترین عدد آن، بلندترین زیررشته‌ی تکرارشونده را می‌دهد.

روش کاسای

اگر پسوندها را به ترتیب متن (نه ترتیب مرتب) برویم، LCP هر بار حداکثر یکی کم می‌شود؛ پس h را از مقدار قبلی منهای یک ادامه می‌دهیم و کل کار O(n) است.

در trace به چه چیزی نگاه کنی

جدول پسوندهای مرتب است و ستون LCP به ترتیب متن پر می‌شود؛ اشاره‌گرهای i و j دو پسوندی‌اند که مقایسه می‌شوند.