珈貓的小窩

摘要： 后綴數(shù)組 學(xué)習(xí)筆記 定義 包含 \(sa\) 和 \(rk\) 兩個數(shù)組，其含義如下： \(sa_i\) 表示：將所有后綴按字典序排序后，在第 \(i\) 位的后綴的第一位下標(biāo)。 \(rk_i\) 表示：將所有后綴按字典序排序后，第一位下標(biāo)為 \(i\) 的后綴的排名。 其中 \(sa\) 是我們所 閱讀全文

摘要： 廣義后綴自動機 學(xué)習(xí)筆記 概述 廣義后綴自動機（General Suffix Automaton）是將后綴自動機整合到字典樹中來解決對于多個字符串的子串問題。 定義 字符串集合 \(\set{s}\) 的廣義后綴自動機（GSAM）是一個接受 \(\set{s}\) 的所有字符串的所有后綴的最小 DF 閱讀全文

摘要： 后綴自動機 學(xué)習(xí)筆記 概述 后綴自動機（suffix automaton, SAM）是一個能解決許多字符串相關(guān)問題的有力的數(shù)據(jù)結(jié)構(gòu)。 直觀上，字符串的 SAM 可以理解為給定字符串的 所有子串 的壓縮形式。 定義 字符串 \(s\) 的后綴自動機（SAM）是一個接受 \(s\) 的所有后綴的最小 D 閱讀全文