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/09 23:38] eyliaw |
lecture_notes:04-22-2011 [2011/06/09 23:56] eyliaw |
||
---|---|---|---|
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]. | ||
- | ^ B_X[0,i]: ^ O_X(G,i): ^ O_X(L,i) ^ O_X(O,i) | + | ^ i ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^ |
- | | 1 L | 0 | 1 | 0 | + | | 1 | L | 0 | 1 | 0 | |
- | | 2 LO | 0 | 1 | 1 | + | | 2 | LO | 0 | 1 | 1 | |
- | | 3 LO$ | 0 | 1 | 1 | + | | 3 | LO$ | 0 | 1 | 1 | |
- | | 4 LO$O | 0 | 1 | 2 | + | | 4 | LO$O | 0 | 1 | 2 | |
- | | 5 LO$OO | 0 | 1 | 3 | + | | 5 | LO$OO | 0 | 1 | 3 | |
- | | 6 LO$OOG | 1 | 1 | 3 | + | | 6 | LO$OOG | 1 | 1 | 3 | |
- | | 7 LO$OOGG | 2 | 1 | 3 | + | | 7 | LO$OOGG | 2 | 1 | 3 | |
- | | + | There are then two recursive formulas to find the start and end positions of a substring: |
+ | End R_(aW) = C(a) + O(a,R_(W) - 1) + 1 or 1 if W is the empty string | ||
+ | Start R-(aW) = C(a) + O(a,R-(W)) or n - 1 if W is the empty string | ||
+ | Where a is the first character and W is the word. | ||
+ | |||
+ | To find the end position of the substring GO in |