資料結(jié)構(gòu)與演算法-wenkub
2022-08-18 17:24:15 本頁面
【正文】 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 [5,8] [5,8] [5,8] [5,8] [4,8] [1,1] [2,2] [3,3] 24 S = a a a a b b b b [5,8] [5,8] [5,8] [5,8] [4,8] [1,1] [2,2] [3,3] 25 26 [1,1] [2,3] [4,8] [7,8] [4,8] [7,8] [4,8] [7,8] [3,3] [3,3] [3,3] [1,1] [3,3] [2,3] [7,8] [4,8] [7,8] [4,8] [7,8] [4,8] 27 [3,3] [1,1] [3,3] [2,3] [7,8] [4,8] [7,8] [4,8] [7,8] [4,8] 28 ? The space plexity of suffix tree ? O(|S|) ? O(|S| log |S|) ? O(|S|2) ? O(|S|3) ? Why? ? Number of nodes = O(|S|). ? Number of edges = O(|S|). ? Space required by each edge = O(1). 29 Constructing Suffix Tree in Linear Time 30 ? [Weiner, IEEE FOCS 1973] ? Linear time but expensive in space. ? D. E. Knuth: “the algorithm of 1973”. ? [McCreight, J. ACM 1976] ? Linear time and quadratic space. ? [Ukkonen, Algorithmica 1995] ? Linear time and linear space. ? Much better readability. 31 32 ? Let T(k) denote the suffix tree of S[1…k]. ? Framework pute T(1)。 ? At the end of each iteration, if a growing point is an internal node, then all latter (higher) growing points are also internal. ? Why? 50 b b a b b a b a b b a a b b a b b a b a a 51 ? The ith growing point = the end of the ith suffix S[i…k] of the current prefix S[1…k]. ? Argument: ? the ith (i k) growing point is internal. ? S[i…k]a or S[i...k]b is a substring of S[1…k]. ? S[i+1…k]a or S[i+1...k]b is a substring of S[1…k]. ? The (i+1)st growing point is internal. 52 b b a b b a b a b b a a b b a b b a b a a 53 ? At the end of the current iteration, its corresponding growing point is still an internal node. 54 b b a b b a b a b b a a b b a b b a b a a 55 ? At the end of each iteration, if a growing point is an internal node, then all latter (higher) growing points are also internal. ? Therefore, in “t
公司管理相關(guān)推薦
鄂ICP備17016276號-1