把一個字串的所有後綴照字典序排好。排好之後,子串搜尋、找重複、比較全都變快。
banana 帶你看 SA 怎麼長出來、LCP 怎麼揪出重複。
後綴 = 從某位置到結尾 —— banana 的後綴有 banana、anana、nana、ana、na、a(共 6 個,對應起始位置 0~5)。
SA = 排序後的起始位置 —— 把 6 個後綴照字典序排好,記下起始位置:SA = [5, 3, 1, 0, 4, 2]。SA 存的是位置編號,不是後綴字串本身。
開頭相同的後綴會擠在一起 —— 排完序,a、ana、anana 自然排在相鄰位置。這正是找「重複」的線索。
子串搜尋變二分 —— 一個模式若在字串裡出現,它一定是某些後綴的前綴;SA 排好序,就能像查字典一樣二分搜尋。
LCP[i] = 排序後第 i 與第 i−1 個後綴的最長共同前綴 —— 例如 ana 和 anana 共享 ana,LCP=3。
最大 LCP = 最長重複子串 —— 一段字串重複出現,代表有兩個後綴以它開頭;排序後這兩個後綴會相鄰,它們的 LCP 就是那段重複。取最大的 LCP 就找到最長重複子串。
不同子串個數有公式 —— 全部子串有 n(n+1)/2 個,扣掉重複算到的:不同子串 = n(n+1)/2 − Σ LCP。
Kasai 演算法 O(n) 算 LCP —— 有了 SA,用一個聰明的順序(按原字串位置)算 LCP,只要線性時間。
O(n))。O(n² log n)(每次字串比較最壞 O(n)),字串一長就爆。實務用倍增法 O(n log n) 或更強的 SA-IS O(n)。這頁的視覺化用小字串,樸素排序就夠看。SA 就像把所有後綴當詞條排進字典。排好之後,要查某個開頭就能二分翻,不用一頁頁找。
基因序列裡找最長重複片段、比對相似區段,後綴陣列 + LCP 是常見利器。
一旦所有後綴排好序,子串搜尋、找重複、算不同子串…一堆問題都跟著變簡單。
列出 banana 的 6 個後綴 → 照字典序排好成 SA → 算相鄰的 LCP(琥珀=共同前綴)→ 最大的 LCP 就是最長重複子串(綠色)。按「下一步」。
從樸素建 SA、倍增法、Kasai 算 LCP,到最長重複子串、不同子串個數、二分搜尋子串,再到 LCP 觀念、對照後綴樹、應用與小結。
❌ 樸素排序對長字串太慢 —— sorted(range(n), key=后綴) 是 O(n² log n),幾萬字元就卡。長字串用倍增法或 SA-IS。
❌ 以為 SA 存的是後綴字串 —— SA 存的是起始位置(整數),要看字串再用 s[SA[i]:] 取。
❌ 忘了 LCP 只算相鄰 —— LCP 陣列只有「排序後相鄰」兩後綴的值。任意兩後綴的 LCP = 它們之間所有相鄰 LCP 的最小值(用 RMQ / 稀疏表)。
❌ 小問題硬上 SA —— 只找一個子串用 KMP、找重複用雜湊可能更快更短。SA 適合「同一字串要反覆做很多種查詢」。
banana 的 SA 是什麼?LCP 的最大值在哪、對應到哪個重複子串?n(n+1)/2 − Σ LCP?那個 Σ LCP 扣掉的是什麼?把答案打到對話裡,我幫你對。