This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
lecture_notes:04-22-2011 [2011/06/08 17:29] eyliaw [Suffix array] |
lecture_notes:04-22-2011 [2011/06/09 23:41] eyliaw [Searching] |
||
---|---|---|---|
Line 21: | Line 21: | ||
6 $GOOGOL | 6 $GOOGOL | ||
Sort: | Sort: | ||
- | 6 $GOOGO**L** | + | 6 $GOOGOL |
- | 3 GOL$GO**O** | + | 3 GOL$GOO |
- | 0 GOOGOL**$** | + | 0 GOOGOL$ |
- | 5 L$GOOG**O** | + | 5 L$GOOGO |
- | 2 OGOL$G**O** | + | 2 OGOL$GO |
- | 4 OL$GOO**G** | + | 4 OL$GOOG |
- | 1 OOGOL$**G** | + | 1 OOGOL$G |
S(i) = [6,3,0,5,2,4,1] | S(i) = [6,3,0,5,2,4,1] | ||
Line 41: | Line 41: | ||
O 4 | O 4 | ||
O_X(a,i) is the number of occurrences of a in B_X[0,i]. | O_X(a,i) is the number of occurrences of a in B_X[0,i]. | ||
+ | ^ i ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^ | ||
+ | | 1 | L | 0 | 1 | 0 | | ||
+ | | 2 | LO | 0 | 1 | 1 | | ||
+ | | 3 | LO$ | 0 | 1 | 1 | | ||
+ | | 4 | LO$O | 0 | 1 | 2 | | ||
+ | | 5 | LO$OO | 0 | 1 | 3 | | ||
+ | | 6 | LO$OOG | 1 | 1 | 3 | | ||
+ | | 7 | LO$OOGG | 2 | 1 | 3 | | ||
+ | |||
+ | |