資料結構與演算法-全文預覽
【正文】 a b b a a b b b a a b b a a b a a b a b b The challenges: How do we derive the position of the current growing point? ? Vertically (case 2) ? Horizontally (case 3) ? Q: Which one is easier? 80 ? Moving from iteration k – 1 to iteration k. ? The growing point does not move! ? This is the easier case. Case 2: 節(jié)外生枝 Case 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 81 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 Case 1: 長此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 82 ? Moving from Step i to Step i+1 in the same iteration. ? The growing point moves dramatically. ? This is the tougher case. Case 2: 節(jié)外生枝 Case 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 83 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 Case 1: 長此以往 Case 2: 節(jié)外生枝 Case 3: 若無其事 84 「前人種樹後人涼」的哲學 85 ? 每次千辛萬苦找到 vertical movement的目的時 , 把這個 movement的起點與終點用一個 link記錄下來 . ? 下回遇到這個起點時 , 就可以直接走到終點去 ,不用再重新找一次 . ? 這些 link就叫做 suffix link (斷頭指標 ). 86 ? 終點所對應的字串 ,是起點所對應之字串的「斷頭字串」 (second suffix) Case 2: 節(jié)外生枝 Case 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 87 ? 每個「斷頭指標」的起點一定是個 internal node, ? 不會葉子 ? 不會是某個 suffix tree edge的中間 ? Why? Case 2: 節(jié)外生枝 Case 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 88 ? 每個 internal node一定是某個「斷頭指標」的起點 ? Why? Case 2: 節(jié)外生枝 Case 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 89 S = b b a b b a a b [1,] [2,] [3,] [3,] [3,3] [7,] [4,] [3,3] [7,] [4,] [2,3] [7,] [4,] 1 [1,1] 1 2 1 1 1 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 90 ? Going up to a closest internal node (whose suffix link must be available). Suppose this upward traversal passes through t characters. ? Following the suffix link that starts from this internal node. t [i, j] 91 ? Going down by matching the tcharacter substring S[i, i + t – 1] of S. t [i, j] 92 ? Na239。 33 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 34 b b a b b a a b b a b b a a b a b b a a b
公司管理相關推薦
鄂ICP備17016276號-1