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:56] eyliaw |
lecture_notes:04-22-2011 [2011/06/09 23:57] eyliaw [Searching] |
||
---|---|---|---|
Line 49: | Line 49: | ||
| 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: | + | 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 | 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 | + | 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. | Where a is the first character and W is the word. | ||
To find the end position of the substring GO in | To find the end position of the substring GO in |