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

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 on geeksforgeeks