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

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
i012345S[i]banana
นำข้อความมาทำเป็นอักษรย่อยแล้วเรียงตามindex
suffixibanana 0anana 1nana 2ana 3na 4a 5
เรียงตามลำดับ suffix array ของอักษรย่อย S
suffixia5ana3anana1banana0na4nana2
จากนั้นให้เราหาจำนวนอักษรที่ยาวที่สุดของ suffix arrayตามลำดับจะได้ LCP array
isuffixLCP array5a03ana11anana30banana04na02nana2
เราจะได้ 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  on geeksforgeeks

หมวดหมู่:แถวลำดับ
หมวดหมู่:ดัชนีสายอักขระย่อย
หมวดหมู่:โครงสร้างข้อมูลสายอักขระ