GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — JavaScript/Search/StringSearch.js at master · TheAlgorithms/JavaScript Expand file tree/ Copy pathStringSearch.jsMore file actions 83 lines (77 loc) · 2.89 KB / Copy pathStringSearch.jsFile metadata and controls83 lines (77 loc) · 2.89 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 /* * String Search */ function makeTable(str) { // create a table of size equal to the length of `str` // table[i] will store the prefix of the longest prefix of the substring str[0..i] const table = new Array(str.length) let maxPrefix = 0 // the longest prefix of the substring str[0] has length table[0] = 0 // for the substrings the following substrings, we have two cases for (let i = 1; i < str.length; i++) { // case 1. the current character doesn't match the last character of the longest prefix while (maxPrefix > 0 && str.charAt(i) !== str.charAt(maxPrefix)) { // if that is the case, we have to backtrack, and try find a character that will be equal to the current character // if we reach 0, then we couldn't find a character maxPrefix = table[maxPrefix - 1] } // case 2. The last character of the longest prefix matches the current character in `str` if (str.charAt(maxPrefix) === str.charAt(i)) { // if that is the case, we know that the longest prefix at position i has one more character. // for example consider `.` be any character not contained in the set [a.c] // str = abc....abc // consider `i` to be the last character `c` in `str` // maxPrefix = will be 2 (the first `c` in `str`) // maxPrefix now will be 3 maxPrefix++ // so the max prefix for table[9] is 3 } table[i] = maxPrefix } return table } // Find all the words that matches in a given string `str` export function stringSearch(str, word) { // find the prefix table in O(n) const prefixes = makeTable(word) const matches = [] // `j` is the index in `P` let j = 0 // `i` is the index in `S` let i = 0 while (i < str.length) { // Case 1. S[i] == P[j] so we move to the next index in `S` and `P` if (str.charAt(i) === word.charAt(j)) { i++ j++ } // Case 2. `j` is equal to the length of `P` // that means that we reached the end of `P` and thus we found a match // Next we have to update `j` because we want to save some time // instead of updating to j = 0 , we can jump to the last character of the longest prefix well known so far. // j-1 means the last character of `P` because j is actually `P.length` // e.g. // S = a b a b d e // P = `a b`a b // we will jump to `a b` and we will compare d and a in the next iteration // a b a b `d` e // a b `a` b if (j === word.length) { matches.push(i - j) j = prefixes[j - 1] // Case 3. // S[i] != P[j] There's a mismatch! } else if (str.charAt(i) !== word.charAt(j)) { // if we found at least a character in common, do the same thing as in case 2 if (j !== 0) { j = prefixes[j - 1] } else { // else j = 0, and we can move to the next character S[i+1] i++ } } } return matches } // stringSearch('Hello search the position of me', 'pos') |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |