Python - หา Distinct Palindromic Substrings ทั้งหมด

ได้สตริงตัวพิมพ์เล็ก ASCII ต้องการหา distinct continuous palindromic substrings ทั้งหมด (ไม่ซ้ำ)

ตัวอย่าง

Input: "bddaaa"

Output: [a, aa, aaa, b, d, dd]

อัลกอริธึม: Manacher's Algorithm แบบปรับ (O(n))

Manacher's algorithm หา longest palindrome ทุก center ใน O(n) แล้วเก็บ distinct substrings

def find_distinct_palindromic_substrings(s):
    """Manacher's algorithm variant for distinct palindromes"""
    n = len(s)
    if n == 0:
        return []
    
    # Transform: add boundaries to handle even/odd uniformly
    # "bddaaa" → "@b#d#d#a#a#a#"
    t = '@#' + '#'.join(s) + '#$'
    n_t = len(t)
    
    # P[i] = radius of palindrome centered at i
    P = [0] * n_t
    center = right = 0
    
    for i in range(1, n_t - 1):
        mirror = 2 * center - i
        
        if i < right:
            P[i] = min(right - i, P[mirror])
        
        # Expand
        while t[i + P[i] + 1] == t[i - P[i] - 1]:
            P[i] += 1
        
        # Update center/right
        if i + P[i] > right:
            center, right = i, i + P[i]
    
    # Extract distinct palindromes
    palindromes = set()
    
    for i in range(1, n_t - 1):
        # Length of palindrome in original string
        max_len = P[i]
        # Start index in original string
        start = (i - max_len) // 2
        
        # Add all lengths from 1 to max_len
        for length in range(1, max_len + 1):
            # Only add if valid palindrome in original
            orig_start = (i - length) // 2
            orig_end = orig_start + length
            if 0 <= orig_start < orig_end <= n:
                palindromes.add(s[orig_start:orig_end])
    
    return sorted(palindromes)

# ทดสอบ
print(find_distinct_palindromic_substrings("bddaaa"))
# ['a', 'aa', 'aaa', 'b', 'd', 'dd']

Simple Approach: Expand Around Center + Set (O(n²))

สำหรับสตริงสั้นหรือไม่ต้องการ optimize ใช้วิธีนี้เข้าใจง่ายกว่า:

def find_distinct_palindromes_simple(s):
    palindromes = set()
    n = len(s)
    
    for center in range(2 * n - 1):
        left = center // 2
        right = left + center % 2
        
        while left >= 0 and right < n and s[left] == s[right]:
            palindromes.add(s[left:right+1])
            left -= 1
            right += 1
    
    return sorted(palindromes)

# ทดสอบ
print(find_distinct_palindromes_simple("bddaaa"))
# ['a', 'aa', 'aaa', 'b', 'd', 'dd']

ตัวอย่างเพิ่มเติม

test_cases = [
    "bddaaa",      # ['a', 'aa', 'aaa', 'b', 'd', 'dd']
    "ababa",       # ['a', 'aba', 'ababa', 'b', 'bab']
    "aaaa",        # ['a', 'aa', 'aaa', 'aaaa']
    "abc",         # ['a', 'b', 'c']
    "",            # []
    "a",           # ['a']
]

for s in test_cases:
    result = find_distinct_palindromes_simple(s)
    print(f"'{s}' -> {result}")

ผลลัพธ์

'bddaaa' -> ['a', 'aa', 'aaa', 'b', 'd', 'dd']
'ababa' -> ['a', 'aba', 'ababa', 'b', 'bab']
'aaaa' -> ['a', 'aa', 'aaa', 'aaaa']
'abc' -> ['a', 'b', 'c']
'' -> []
'a' -> ['a']

Complexity Comparison

Palindromic Tree (Eertree) - Advanced

class PalindromicTree:
    """Eertree - หา distinct palindromes ใน O(n)"""
    def __init__(self):
        self.tree = [{'len': -1, 'link': 0, 'next': {}},  # root1 (odd)
                     {'len': 0, 'link': 0, 'next': {}}]   # root2 (even)
        self.s = ['#']  # dummy
        self.last = 1
        self.num = 2
    
    def add_char(self, ch):
        self.s.append(ch)
        cur = self.last
        while True:
            cur_len = self.tree[cur]['len']
            if len(self.s) - 2 - cur_len >= 0 and self.s[len(self.s) - 2 - cur_len] == ch:
                break
            cur = self.tree[cur]['link']
        
        if ch in self.tree[cur]['next']:
            self.last = self.tree[cur]['next'][ch]
            return
        
        self.tree.append({'len': self.tree[cur]['len'] + 2, 'link': 0, 'next': {}})
        self.tree[cur]['next'][ch] = self.num
        
        if self.tree[self.num]['len'] == 1:
            self.tree[self.num]['link'] = 1
        else:
            link_cur = self.tree[cur]['link']
            while True:
                link_len = self.tree[link_cur]['len']
                if len(self.s) - 2 - link_len >= 0 and self.s[len(self.s) - 2 - link_len] == ch:
                    break
                link_cur = self.tree[link_cur]['link']
            self.tree[self.num]['link'] = self.tree[link_cur]['next'][ch]
        
        self.last = self.num
        self.num += 1
    
    def get_palindromes(self):
        result = []
        for i in range(2, self.num):
            length = self.tree[i]['len']
            # reconstruct palindrome (ต้องเก็บเพิ่ม)
            result.append(length)
        return result

สรุป

• Simple (O(n²)): Expand around center + Set - ใช้งานง่าย สำหรับ n ≤ 1000
• Manacher's (O(n)): Optimal สำหรับหา longest แต่ extract all ต้องเพิ่ม logic
• Eertree (O(n)): Purpose-built สำหรับ distinct palindromes
• Output size สูงสุด O(n²) (เช่น "aaaaa" มี n(n+1)/2 palindromes)