資料結(jié)構(gòu)與演算法(已修改)
2025-08-02 17:24 本頁面
【正文】 臺大資工系 呂學一 1 2 ? 字尾樹、後綴樹 … ? an extremely powerful data structure for string algorithms 3 ? Input: P and S. ? Output: All occurrences of P in S. ? Time: O(|P| + |S|) ? Technique: Z values of PS. ? Z(i + |P|) ≥ |P| iff P = S[i…i + |P| – 1]. P S 4 ? Preprocessing P ? Gusfield ? BoyerMoore ? KnuthMorrisPratt ? Preprocessing S ? Suffix tree 5 6 S = b b a b b a a b S[1…8]= b b a b b a a b S[2…8]= b a b b a a b S[3…8]= a b b a a b S[4…8]= b b a a b S[5…8]= b a a b S[6…8]= a a b S[7…8]= a b S[8…8]= b 1st suffix 2nd suffix 3rd suffix 4th suffix 5th suffix 6th suffix 7th suffix 8th suffix 7 S = b b a b b a a b S[1…8]= b b a b b a a b S[2…8]= b a b b a a b S[3…8]= a b b a a b S[4…8]= b b a a b S[5…8]= b a a b S[6…8]= a a b S[7…8]= a b S[8…8]= b 1st suffix 2nd suffix 3rd suffix 4th suffix 5th suffix 6th suffix 7th suffix 8th suffix 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 9 ? The following statements are equivalent. ? P occurrs in S. ? P is a prefix of a suffix of S. ? P corresponds to a path of T starting from the root of T. 10 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b P occurs in S! 11 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b P doesn’t occur in S! 12 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b P doesn’t occur in S! 13 14 8 4 4 4 4 1 1 1 1 1 5 5 5 2 2 2 2 2 6 7 6 3 3 3 7 3 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b Output: 3 15 ?Question: ?If we are given a suffix trie of S, what is the time plexity for finding an occurrence of P in S? ?Answer: ?O(|P|) time. 16 Q: Time plexity for constructing the suffix trie T of S? Q(|S|) Q(|S| log |S|) Q(|S|2) Q(|S|3) 17 8 4 4 4 4 1 1 1 1 1 5 5 5 2 2 2 2 2 6 7 6 3 3 3 7 3 1 2 3 4 5 6 7 8 b b a b b a a b b a b b a a b a b b a a b b b a a b b a a b a a b a b b 18 ? How to establish a lower bound? ? Answer: ? Showing an example which takes W(|S|2) time for any algorithm. 19 20 ? Suffix trie is good in solving Substring Problem, but may require W(|S|2) time and space. ? Question: is there a pact representation of suffix trie that needs only O(|S|) time and space? 21 A pact representation of suffix trie 22 ? T has at most |S| leaves. ? Why? ? T has at most |S| – 1 branching nodes. ? Why? 23 ? Keeping leaves and branching nodes only. ? pact representation of edge labels S = a a a a b b b b
公司管理相關(guān)推薦
鄂ICP備17016276號-1