Python - หา Substrings แบบ Palindromic ทั้งหมด (รวมซ้ำ)

ได้สตริง ต้องการหา substrings แบบ palindromic ทั้งหมด นับซ้ำได้ (เช่น "aa" ปรากฏ 2 ครั้ง นับ 2)

ตัวอย่าง

Input: "redivider"

Output: ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r'] (13 substrings)

อัลกอริธึม: Expand Around Center

ใช้ "center expansion" โดยพิจารณา center ทุกตำแหน่ง (รวมระหว่างตัวอักษร)

def get_all_palindromic_substrings(s):
    """หา palindromic substrings ทั้งหมด (รวม duplicate)"""
    result = []
    n = len(s)
    
    # Center positions: 0, 0.5, 1, 1.5, ..., n-1
    # pos = integer → odd length palindrome (center at character)
    # pos = half-integer → even length palindrome (center between characters)
    
    pos = 0.0
    while pos < n:
        rad = pos - int(pos)  # 0 for odd, 0.5 for even
        
        # Expand around center
        while (pos + rad < n and 
               pos - rad >= 0 and 
               s[int(pos - rad)] == s[int(pos + rad)]):
            
            start = int(pos - rad)
            end = int(pos + rad + 1)
            result.append(s[start:end])
            
            rad += 1
        
        pos += 0.5
    
    return result

# ทดสอบ
s = "redivider"
palindromes = get_all_palindromic_substrings(s)
print(f"Count: {len(palindromes)}")
print(palindromes)

ผลลัพธ์

Count: 13
['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

การทำงานแบบ Visualize

String:  r  e  d  i  v  i  d  e  r
Index:   0  1  2  3  4  5  6  7  8

Centers (pos):
0.0  → center at 'r'     → "r"
0.5  → between r|e       → (no match)
1.0  → center at 'e'     → "e"
1.5  → between e|d       → (no match)
2.0  → center at 'd'     → "d"
2.5  → between d|i       → (no match)
3.0  → center at 'i'     → "i"
3.5  → between i|v       → (no match)
4.0  → center at 'v'     → "v", "ivi", "divid", "edivide", "redivider"
4.5  → between v|i       → (no match)
5.0  → center at 'i'     → "i"
5.5  → between i|d       → (no match)
6.0  → center at 'd'     → "d"
6.5  → between d|e       → (no match)
7.0  → center at 'e'     → "e"
7.5  → between e|r       → (no match)
8.0  → center at 'r'     → "r"

Alternative: Manacher's Algorithm (O(n))

สำหรับหา longest palindromic substring ใช้ Manacher's algorithm O(n) แต่สำหรับหา "ทั้งหมด" ต้องใช้ O(n²) อยู่ดี เพราะ output เองก็มีขนาด O(n²) ใน worst case (เช่น "aaaaa")

เวอร์ชันที่อ่านง่ายกว่า (ไม่ใช้ float)

def get_palindromes_readable(s):
    result = []
    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]:
            result.append(s[left:right+1])
            left -= 1
            right += 1
    
    return result

Unique Palindromes (ไม่ซ้ำ)

def get_unique_palindromes(s):
    return list(set(get_all_palindromic_substrings(s)))

# หรือ modify algorithm ให้เก็บใน set
def get_unique_palindromes_direct(s):
    unique = 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]:
            unique.add(s[left:right+1])
            left -= 1
            right += 1
    return sorted(unique, key=lambda x: (len(x), x))

Complexity

• Time: O(n²) - worst case ทุก substring เป็น palindrome
• Space: O(n²) - สำหรับเก็บผลลัพธ์
• Output-sensitive: เหมาะสมเพราะ output ใหญ่