高級(jí)數(shù)據(jù)結(jié)構(gòu)深度解析如何用后綴自動(dòng)機(jī)與線段樹高效解決字符串和區(qū)間問題【免費(fèi)下載鏈接】AlgorithmsSeveral algorithms and data structures implemented in C by me (credited to others where necessary).項(xiàng)目地址: https://gitcode.com/gh_mirrors/algorithms174/Algorithms對(duì)于準(zhǔn)備算法競(jìng)賽或想深入理解 C 數(shù)據(jù)結(jié)構(gòu)的新手來說后綴自動(dòng)機(jī)和線段樹是兩塊繞不開的基石。本文基于開源項(xiàng)目 algorithms174/Algorithms 中的真實(shí)實(shí)現(xiàn)Suffix Automaton.cpp 與 Segment Tree.cpp用通俗語言拆解這兩種高級(jí)數(shù)據(jù)結(jié)構(gòu)的工作原理、時(shí)間復(fù)雜度和典型用法幫助你快速建立清晰的概念。 為什么需要高級(jí)數(shù)據(jù)結(jié)構(gòu)數(shù)組、鏈表解決的是存取問題而后綴自動(dòng)機(jī)和線段樹解決的是查詢效率問題數(shù)據(jù)結(jié)構(gòu)解決的核心問題典型應(yīng)用場(chǎng)景后綴自動(dòng)機(jī)字符串的子串匹配、最長(zhǎng)公共子串文本檢索、基因序列比對(duì)線段樹區(qū)間最值/求和 單點(diǎn)修改區(qū)間統(tǒng)計(jì)、實(shí)時(shí)數(shù)據(jù)更新這個(gè)項(xiàng)目最初源于算法競(jìng)賽作者用 C 實(shí)現(xiàn)了一大批競(jìng)賽級(jí)數(shù)據(jù)結(jié)構(gòu)全部采用 MIT 許可證你可以自由取用。 后綴自動(dòng)機(jī)字符串界的萬能字典什么是后綴自動(dòng)機(jī)一句話概括它是一個(gè)能識(shí)別出給定字符串所有子串的最小的狀態(tài)機(jī)DFA。你可以把它想象成一個(gè)字符串字典——只要字符逐個(gè)喂進(jìn)去它就能記住這個(gè)字符串包含哪些片段以及每個(gè)片段出現(xiàn)的位置關(guān)系。它的強(qiáng)大之處在于兩個(gè)關(guān)鍵性質(zhì)狀態(tài)數(shù)很少長(zhǎng)度為 n 的字符串狀態(tài)數(shù)最多只有2n-1個(gè)構(gòu)建極快逐字符擴(kuò)展整體時(shí)間復(fù)雜度為O(n)。項(xiàng)目中的實(shí)現(xiàn)方式打開 Suffix Automaton.cpp核心只有三步詳見文件內(nèi)注釋說明init_automaton()初始化起始狀態(tài)extend_automaton(char)每讀入一個(gè)新字符就擴(kuò)展一次必要時(shí)復(fù)制并克隆狀態(tài)即經(jīng)典的clone 操作lcs(needle)拿著第二個(gè)字符串走自動(dòng)機(jī)邊走邊記錄當(dāng)前匹配長(zhǎng)度一旦走不下去就沿后綴鏈回退最終取出最長(zhǎng)匹配段。文件頭部注釋明確給出了復(fù)雜度構(gòu)建自動(dòng)機(jī) O(n)求兩字符串的最長(zhǎng)公共子串LCSO(m)真實(shí)運(yùn)行效果對(duì)示例字符串s1 alsdfkjfjkdsal與s2 fdjskalajfkdsla求最長(zhǎng)公共子串程序輸出kds——三個(gè)字符恰好就是兩段字符串共同擁有的最長(zhǎng)連續(xù)片段。對(duì)比后綴數(shù)組 LCP 數(shù)組項(xiàng)目中還收錄了 Suffix Array LCP Array.cpp思路完全不同把所有后綴排序再用 LCP 數(shù)組記錄相鄰后綴的最長(zhǎng)公共前綴。以經(jīng)典例子banana為例它輸出的是排序后的后綴起點(diǎn)位置和對(duì)應(yīng)的 LCP 數(shù)組。維度后綴自動(dòng)機(jī)后綴數(shù)組 LCP構(gòu)建復(fù)雜度O(n)O(n log2n)額外信息子串出現(xiàn)次數(shù)等后綴的字典序、LCP代碼特點(diǎn)需要理解 clone 狀態(tài)轉(zhuǎn)移倍增排序更直觀適用傾向在線逐字符擴(kuò)展的場(chǎng)景離線批量查詢的場(chǎng)景 線段樹區(qū)間問題的瑞士軍刀什么是線段樹把數(shù)組遞歸地二分成一棵二叉樹每個(gè)節(jié)點(diǎn)負(fù)責(zé)一段連續(xù)區(qū)間并保存該區(qū)間的匯總信息比如最小值。這樣查詢區(qū)間 [l, r]時(shí)只需訪問 O(log N) 個(gè)節(jié)點(diǎn)而不是遍歷整個(gè)區(qū)間修改某個(gè)位置時(shí)只需沿一條從葉到根的路徑更新同樣 O(log N)。項(xiàng)目中的最小可用實(shí)現(xiàn)Segment Tree.cpp 是一個(gè)麻雀雖小五臟俱全的版本只用三個(gè)遞歸函數(shù)就實(shí)現(xiàn)了區(qū)間最小值查詢 單點(diǎn)更新函數(shù)作用復(fù)雜度InitTree自底向上建立最小值樹O(N)Update修改單個(gè)位置并刷新路徑上的最小值O(log N)Query查詢?nèi)我鈪^(qū)間的最大值/最小值O(log N)真實(shí)運(yùn)行效果對(duì)數(shù)組[4, 2, 5, 1, 6, 3]建樹后查詢區(qū)間[1,3]的最小值得到2接著把第 4 位改成 10、第 5 位改成 0再查詢區(qū)間[4,6]最小值立刻變成0。整個(gè)過程只用了不到 100 行 C。 兩張圖怎么選遇到字符串子串匹配、公共子串問題 → 首選后綴自動(dòng)機(jī)O(n) 構(gòu)建后續(xù)每個(gè)查詢字符串只需 O(m)遇到頻繁區(qū)間統(tǒng)計(jì) 單點(diǎn)修改問題 → 首選線段樹建樹 O(N) 后每次操作都是 O(log N)如果你的字符串查詢偏離線、還需要字典序能力 → 可以參考后綴數(shù)組 LCP方案。 快速上手這個(gè)項(xiàng)目克隆倉(cāng)庫(kù)git clone https://gitcode.com/gh_mirrors/algorithms174/Algorithms進(jìn)入 Data Structures/ 目錄目標(biāo)文件都在Data Structures文件夾內(nèi)用 g 直接編譯即可運(yùn)行例如g Data Structures/Segment Tree.cpp -o segtree ./segtree項(xiàng)目?jī)?nèi)還有大量同類實(shí)現(xiàn)可供橫向?qū)W習(xí)比如Binary Indexed Tree.cpp樹狀數(shù)組線段樹的輕量近親Trie.cpp字典樹字符串前綴的經(jīng)典結(jié)構(gòu)Fenwick/Segment 變體之外還有后綴數(shù)組與自動(dòng)機(jī)對(duì)照閱讀效果更佳所有代碼均無授權(quán)限制但請(qǐng)注意倉(cāng)庫(kù)聲明不提供任何保證——建議先讀懂注釋中的復(fù)雜度說明再投入使用。 總結(jié)這篇后綴自動(dòng)機(jī)與線段樹教程帶你完成了三件事理解了它們各自快在哪里、看懂了項(xiàng)目中的最小實(shí)現(xiàn)Suffix Automaton.cpp、Segment Tree.cpp并掌握了選型思路。掌握這兩個(gè)結(jié)構(gòu)后你會(huì)發(fā)現(xiàn)競(jìng)賽和工程里的字符串與區(qū)間問題大多都有現(xiàn)成的優(yōu)雅解法?！久赓M(fèi)下載鏈接】AlgorithmsSeveral algorithms and data structures implemented in C by me (credited to others where necessary).項(xiàng)目地址: https://gitcode.com/gh_mirrors/algorithms174/Algorithms創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考