lecture_notes:04-22-2011
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
lecture_notes:04-22-2011 [2011/06/09 23:57] eyliaw [Searching] |
lecture_notes:04-22-2011 [2011/06/09 23:57] eyliaw [Searching] |
||
|---|---|---|---|
| Line 52: | Line 52: | ||
| 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 | ||
lecture_notes/04-22-2011.txt · Last modified: 2015/08/09 23:06 by 212.129.31.47
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
