Implementation of boyer moore string search O(l) where l=len(text)
(text string, pattern string)
| 3 | // Implementation of boyer moore string search |
| 4 | // O(l) where l=len(text) |
| 5 | func BoyerMoore(text string, pattern string) []int { |
| 6 | var positions []int |
| 7 | |
| 8 | l := len(text) |
| 9 | n := len(pattern) |
| 10 | |
| 11 | // using booyer moore horspool modification |
| 12 | // O(n) space instead of O(n**2) |
| 13 | bcr := make(map[byte]int) |
| 14 | for i := 0; i < n-1; i++ { |
| 15 | bcr[pattern[i]] = n - i - 1 |
| 16 | } |
| 17 | |
| 18 | // Apostolico–Giancarlo modification |
| 19 | // allow to skip patterns that we know matches |
| 20 | // let us do O(l) instead of O(ln) |
| 21 | skips := make(map[int]int) |
| 22 | for _, s := range bcr { |
| 23 | i := 0 |
| 24 | for ; i < n-s; i++ { |
| 25 | if pattern[n-1-i] != pattern[n-1-s-i] { |
| 26 | break |
| 27 | } |
| 28 | } |
| 29 | skips[s] = i |
| 30 | } |
| 31 | |
| 32 | skip := 0 |
| 33 | jump := n |
| 34 | for i := 0; i < l-n+1; { |
| 35 | skip = skips[jump] |
| 36 | for k := n - 1; k > -1; k-- { |
| 37 | if text[i+k] != pattern[k] { |
| 38 | jump, ok := bcr[text[i+k]] |
| 39 | if !ok { |
| 40 | jump = n |
| 41 | } |
| 42 | i += jump |
| 43 | break |
| 44 | } |
| 45 | if k == n-jump { |
| 46 | k -= skip |
| 47 | } |
| 48 | if k == 0 { |
| 49 | positions = append(positions, i) |
| 50 | jump = 1 |
| 51 | i += jump |
| 52 | } |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | return positions |
| 57 | } |
no outgoing calls