算法合集之尋找最大重復(fù)子串-資料下載頁
2024-10-16 20:30本頁面
【正文】 數(shù)的平攤求解復(fù)雜度為 O(1) LsL = 與 U(1+L， |U|)的 最長 公共前綴 LpL = 與 V + U(1， L)的 最長 公共后綴 U V 算法基本框架回顧和完善 字符串分解 answer = 0 令 V = 長度為 |Ui| + 2 * |Ui1|的 P的后綴 U = Ui For i = 2 to m do End For 針對情況 1： S在 V中的長度 = L ? ? End 情況 1 求出函數(shù) Ls和函數(shù) Lp的值 針對情況 2： S在 U中的長度 = L End 情況 2 For L=1 to |Ui1 + Ui|1 do 輸出 answer If |LsL| + |LpL| = L Then 用 L更新 answer的值 算法性能分析 較大 20 10 字符串分解 O (n) O (n) 程序步驟 算法名稱 復(fù)雜度 常數(shù)因子 后綴樹算法 輔助函數(shù) 枚舉所有最優(yōu)子串 O (n) Sum{2(|Ui1|+|Ui|)} = 4n KMP模式匹配 Sum{|Ui1|+|Ui|} = 2n 枚舉 總結(jié) ● 掌握基礎(chǔ)算法 ● 善于分化問題 ● 融會貫通 謝 謝 !
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1