題幹與適用場景
後綴陣列保存文字每個後綴的起點，並按後綴字典序排列。固定文字會收到許多模式查詢時，可以在這個有序索引上找出所有匹配，不必每次從頭掃描。Stanford CS166 題目直接要求實作 searchFor，回傳所有匹配位置並達到 O(n log m + z) 的查詢目標；本文以 m 表示模式長度、n 表示文字長度、z 表示結果數。
面試官考察點
- 能否說明「模式出現」等價於「某個後綴以模式為前綴」。
- 能否用 lower bound 找到匹配區間左右邊界，而非找到一個位置就停止。
- 能否把建構成本與每次查詢成本分開，正確處理 z 個輸出。
- 能否辨識空模式、哨兵、重複後綴與字元比較成本等邊界。
回答前需要釐清的問題
- 文字是否固定、查詢是否很多？若文字也持續變更，後綴陣列的重建成本可能不合適。
- 需要回傳所有起點、出現次數，還是只判斷是否存在？
- 是否區分大小寫、Unicode 正規化或位元組序列？比較函式必須符合業務語義。
- 是否已給定 sa，還是也要實作建構？若要建構，允許教學用排序還是要求線性演算法？
30 秒回答框架
「後綴陣列按後綴字典序排列，所以以 pattern 開頭的後綴一定是連續區間。我寫比較函式，把 pattern 與 text[sa[i]:] 按前綴比較；第一次二分找不小於 pattern 的位置，第二次找大於該前綴的右邊界。區間內每個 sa 值就是一個匹配起點，輸出成本是 O(z)，查詢總成本 O(m log n + z)。空模式按約定回傳 n+1 個位置。」
分步驟深入解答
第一步：建立後綴陣列的語義
文字 banana 的後綴起點按字典序可寫為 [5, 3, 1, 0, 4, 2]。陣列只保存整數起點，不複製後綴內容。MIT 講義強調它是按字典序排列的起點列表，並可在該序列上二分。
第二步：把匹配變成區間
所有以 ana 開頭的後綴會相鄰，因此答案不是一個點，而是一個半開區間 [left, right)。比較器只需區分三種結果：目前後綴前綴小於 pattern、相等或大於 pattern。相等時向左或向右繼續收縮，才能得到完整區間。
第三步：實作兩個 lower bound
第一個 lower bound 的條件是「後綴前綴不小於 pattern」。第二個可以把比較目標定義為「後綴前綴嚴格大於 pattern」，或先找相等區間右端。不能直接把 pattern 當成完整後綴比較；較短後綴是 pattern 的前綴時，結果應視為較小。
第四步：複雜度與建構選擇
若 sa 已給定，每次比較最多檢查 m 個字元，二分進行 O(log n) 次，因此查詢是 O(m log n + z)。Stanford 題目明確把輸出成本單列為 O(z)。教學程式用 sorted(range(n), key=text[i:]) 便於理解，但會複製後綴且很慢；生產應採用 prefix-doubling、SA-IS 或成熟函式庫。MIT 與 Stanford 課程材料都把後綴陣列定位為比後綴樹更省指標空間的固定文字索引。
可執行的 Python 實作
def build_suffix_array(text):
# 教學建構：便於驗證，不代表生產級建構複雜度。
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])程式把建構和查詢分開；最後排序只是為了按文字出現位置回傳結果，若呼叫方接受後綴陣列順序即可省略。空文字、空模式、無匹配與重複匹配都可以直接測試。
高品質示範回答
「我會先確認文字固定且模式很多，然後把每個後綴的起點按字典序存入 sa。由於同一模式是後綴的共同前綴，所有匹配會形成連續區間。我用兩個 lower bound 找區間左右邊界，比較時只看模式長度並把較短後綴視為較小。給定 sa 的查詢複雜度是 O(m log n + z)，其中 z 是輸出數量；空模式回傳 n+1 個邊界位置。教學建構可用排序，但大文字要用 prefix-doubling、SA-IS 或成熟實作，並固定字元正規化規則。」
常見錯誤
- 找到第一個匹配就回傳 → 漏掉相鄰重複後綴 → 二分左右邊界並輸出整個區間。
- 用完整後綴與 pattern 直接比較 → 較短後綴邊界錯誤 → 明確前綴比較和較短後綴規則。
- 把建構複雜度算進每次查詢 → 無法解釋固定文字場景 → 分開報告一次性建構與每次查詢。
- 回傳 sa 區間卻聲稱是文字順序 → 呼叫方結果順序不穩定 → 需要時按起點排序或說明順序契約。
- 忘記空模式的 n+1 個位置 → 與約定不一致 → 在入口先處理空模式。
追問及應對
如果模式長度 m 很大，如何減少重複字元比較？
給相鄰後綴補 LCP 資訊，並在二分時重用已知共同前綴。這樣可以把查詢優化到接近 O(m + log n)，但要額外維護 LCP 與更複雜的搜尋不變量；沒有該增強時應誠實保留 O(m log n)。
文字會頻繁更新時還用後綴陣列嗎？
不應把靜態索引硬套到高頻寫入。可批次重建、按段維護多個索引再合併，或選擇線上匹配結構。決策取決於更新頻率、查詢量與可接受的重建延遲。
如何驗證二分邊界沒有漏結果？
對隨機小文字與模式，用暴力掃描結果和 searchwithsuffix_array 對比；覆蓋空模式、重複字元、模式比文字長、無匹配和所有位置都匹配。邊界斷言應檢查區間外相鄰後綴不滿足前綴條件。
為什麼不能直接用 KMP？
若只有一個模式且文字一次性讀取，KMP 更直接，時間 O(n+m)。後綴陣列的優勢在固定文字、多模式查詢，以及還要支援重複子串、LCP 或 BWT 等離線索引操作時。