Center Expansion (Palindromes & Symmetry) — மைய விரிவு — சமச்சீர் / palindrome

மைய விரிவு — நடு புள்ளியிலிருந்து palindrome வெளியே வளர்த்தல். ஒற்றை நீளத்திற்கு ஒவ்வொரு index; இரட்டை நீளத்திற்கு ஒவ்வொரு இடைவெளி. Manacherக்கு முன் உள்ளுணர்வு.

உண்மை உலகில் இது ஏன் முக்கியம்?

DNA palindrome பகுதிகள் — சமநிலை தேடல். வரைபட ஒப்புமை கருவி — மையக் கோடு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

expand(lo,hi) — பொருந்தும் வரை; நீளம் hi-lo-1. i,i மற்றும் i,i+1 மையங்கள்; அதிகநீளம் பதிவு.

Pythonில் முயற்சி செய்வோம்

def longest_palindrome(s: str) -> str:

    def expand(l: int, r: int) -> tuple[int, int]:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start : end + 1]


print(longest_palindrome("babad"))

அடிக்கடி நேரும் தவறுகள்

• உட்கூறு index ஒற்றைப் பிழை.
• O(n²) — பெரிய உள்ளீடு கவனம்.

முக்கியச் சுருக்கக் குறிப்புகள்

• இரண்டு மைய வகைகள் — ஒற்றை/இரட்டை.
• expand மறுபயன்.