แถวลำดับแอลซีพี

longest common prefix array (LCP array) ถูกนำมาใช้ในปี 1993. โดย Udi Manber และ Gene Myers เพื่อปรับปรุง suffix array การทำงานของวิธีการค้นหาสตริงของพวกเขา โดยวิธีการคือ สมมุติให้มี อาร์เรย์ A: = [aab, ab, abaab, b, baab] เป็น suffix array อักษรที่ยาวที่สุดระหว่าง A [1] = aab และ A [2] = ab เป็นที่มีความยาว 1 ดังนั้น H [2] = 1 ทำนองเดียวกันใน LCP array ของ A [2] = ab และ A [3] = abaab เป็น ab ดังนั้น H [3] = 2

ตัวอย่าง LCP array

สมมุติให้มีว่าข้อความ S = banana ให้เราเรียงตามลำดับindex

i	0	1	2	3	4	5
S[i]	b	a	n	a	n	a

นำข้อความมาทำเป็นอักษรย่อยแล้วเรียงตามindex

suffix	i
banana	0
anana	1
nana	2
ana	3
na	4
a	5

เรียงตามลำดับ suffix array ของอักษรย่อย S

suffix	i
a	5
ana	3
anana	1
banana	0
na	4
nana	2

จากนั้นให้เราหาจำนวนอักษรที่ยาวที่สุดของ suffix arrayตามลำดับจะได้ LCP array

i	suffix	LCP array
5	a	0
3	ana	1
1	anana	3
0	banana	0
4	na	0
2	nana	2

เราจะได้ LCP array ของ S = [0, 1, 3, 0, 0, 2]

การนำ LCP array ไปใช้งานในภาษาPython

ตัวอย่างภาษาไพทอน

def suffix_array(s):
    return [rank for suffix, rank in sorted((s[i:], i) for i in range(len(s)))]

def lcp_array(s):
    
    sa = suffix_array(s)
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]+1] = k;
        if k:
            k -= 1
            
    return lcp

อ้างอิง

LCP array from Suffix Array เก็บถาวร 2017-11-20 ที่ เวย์แบ็กแมชชีน on geeksforgeeks