โจทย์: กำหนดให้มีสตริงพิมพ์เล็ก s ต้องการหาความยาวของซับสตริง (Substring) ที่ปรากฏอย่างน้อย 2 ครั้งใน s หากไม่พบ ให้คืนค่า 0
ตัวอย่าง
Input: s = "abdgoalputabdtypeabd"
Output: 3
เหตุผล: ซับสตริง "abd" ปรากฏ 3 ครั้ง และเป็นซับสตริงซ้ำที่ยาวที่สุด
อัลกอริทึม: Suffix Array + Longest Common Prefix (LCP)
วิธีแก้ปัญหาแบบคลาสสิกคือการสร้าง Suffix Array แล้วหา LCP ระหว่าง Suffix ที่ติดกันในลำดับ Lexicographical
ขั้นตอนการทำงาน
- สร้างรายการ Suffix ทั้งหมดของสตริง
s - เรียงลำดับ Suffix ตาม Lexicographical Order
- เปรียบเทียบคู่ Suffix ที่ติดกัน เพื่อหา Longest Common Prefix (LCP)
- เก็บค่าความยาว LCP สูงสุด
ฟังก์ชัน LCS (Longest Common Substring ของสองสตริง)
def lcs(s1, s2):
n = min(len(s1), len(s2))
for i in range(n):
if s1[i] != s2[i]:
return s1[:i]
return s1[:n]โค้ด Python สมบูรณ์
def lcs(s1, s2):
"""หา Longest Common Prefix ของสองสตริง"""
n = min(len(s1), len(s2))
for i in range(n):
if s1[i] != s2[i]:
return s1[:i]
return s1[:n]
def solve(s):
suffixes = []
n = len(s)
max_len = 0
# สร้าง Suffix ทั้งหมด
for i in range(n):
suffixes.append(s[i:n])
# เรียงลำดับ Suffix
suffixes.sort()
# เปรียบเทียบคู่ที่ติดกัน
for a, b in zip(suffixes, suffixes[1:]):
rtr = lcs(a, b)
if len(rtr) > max_len:
max_len = len(rtr)
return max_len
# ทดสอบ
s = "abdgoalputabdtypeabd"
print(solve(s)) # Output: 3ความซับซ้อน
- Time Complexity: O(n² log n) - เนื่องจากการสร้าง Suffix (O(n²)) และการเรียง (O(n log n) การเปรียบเทียบสตริง O(n))
- Space Complexity: O(n²) - เก็บ Suffix ทั้งหมด
หมายเหตุ: สำหรับข้อมูลขนาดใหญ่ ควรใช้ Suffix Array แบบ O(n log n) หรือ Suffix Automaton (SAM) แบบ O(n) แทน
การปรับปรุงประสิทธิภาพ (Optional)
# ใช้การเปรียบเทียบแบบไม่สร้างสตริงย่อย (Memory Efficient)
def solve_optimized(s):
n = len(s)
suffixes = list(range(n))
suffixes.sort(key=lambda i: s[i:])
max_len = 0
for i in range(n - 1):
a, b = suffixes[i], suffixes[i + 1]
l = 0
while a + l < n and b + l < n and s[a + l] == s[b + l]:
l += 1
max_len = max(max_len, l)
return max_len