| 3 | |
| 4 | var kmp = (function () { |
| 5 | function builtKMPTable(str) { |
| 6 | var res = []; |
| 7 | var len; |
| 8 | var front; |
| 9 | var end; |
| 10 | var found; |
| 11 | for (var i = 1; i <= str.length; i += 1) { |
| 12 | front = Math.max(1, i - ((res[i - 2] || 0) + 1)); |
| 13 | end = Math.min(i - 1, (res[i - 2] || 0) + 1); |
| 14 | found = false; |
| 15 | len = 0; |
| 16 | while (end >= 1 && front <= i && !found) { |
| 17 | if (str.substring(0, end) === str.substring(front, i)) { |
| 18 | found = true; |
| 19 | len = end; |
| 20 | } else { |
| 21 | end -= 1; |
| 22 | front += 1; |
| 23 | } |
| 24 | } |
| 25 | res[i - 1] = len; |
| 26 | } |
| 27 | return res; |
| 28 | } |
| 29 | |
| 30 | /** |
| 31 | * Knuth–Morris–Pratt algorithm. Searches for the position of |