Daily Archives: December 6, 2021

palindrome是指一個字串的 string = reverse(string) 而longest palindromic substring則是指找出一個字串中，substring是palindrome的最長substring 這個問題brute force不難想，就是把所有的substring 列出來，檢查是不是palindrome，但是這樣worse case會是O(n^3)，因為substring有O(n^2)個，檢查palindrom要O(n) 比較常見的做法是中心點展開法，也就是選取一個點，然後展開看最大可以展到多少長度 這樣的time complexity為O(n^2)，共n個字元做展開，每個字元展開worst case O(n), total O(n^2) 事實上，有更好的方法Manacher’s algorithm time complexity是O(n)，可以參考wiki上的說明 https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher’s_algorithm 但是Wiki上的說明實在是太難理解了，所以這邊做個整理說明，並給出一些可能的實現 Manacher’s algorithm中文又有人叫馬拉車算法，本質上還是中心點展開法，但是差異在Manacher算法中會把之前走過的展開的資訊做個紀錄，在後面的展開中直接略去從頭開始展開的步驟，直接將整個演算法步數降到O(n) 在處理palindrome時，為了要避免分開處理奇數長度palindrome 或是偶數長度palindrome，一個常見的處理方式是在字串中插入delimeter 用什麼delimiter都可以，只要不要跟原始string的char衝突就好，加了delimiter後，整個字串的長度一定是奇數，且palindrome也一定是奇數，所以不用擔心要特別偵測偶數的palindrome(偶數palidrome是偵測s[i] == s[i+1]，再以i, i+1往兩側展開) 為什麼加了delimiter就保證奇數呢？可以這樣想: N個字元的字串，有N+1個空間，插入delimeter就是N+N+1 = 2N+1 保證奇數，並且觀察以上abba, aba兩個字串的palindrome，可以發現delimeter本身是對稱的，所以也是符合把palindrome空隙插滿，亦即2m+1的情況，因此也是奇數 這邊先看一下其中一個實現方式，此方法參考了 https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/ … Continue reading →