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/RabinKarp.js at master · hackingstaar/JavaScript Expand file tree/ Copy pathRabinKarp.jsMore file actions 64 lines (54 loc) · 2.16 KB / Copy pathRabinKarp.jsFile metadata and controls64 lines (54 loc) · 2.16 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 /* * Implements the Rabin-Karp algorithm for pattern searching. * * The Rabin-Karp algorithm is a string searching algorithm that uses hashing to find patterns in strings. * It is faster than naive string matching algorithms because it avoids comparing every character in the text. * * This implementation uses a rolling hash function to efficiently compute the hash values of substrings. * It also uses a modulo operator to reduce the size of the hash values, which helps to prevent hash collisions. * * The algorithm returns an array of indices where the pattern is found in the text. If the pattern is not * found, the algorithm returns an empty array. * * [Reference](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm) */ const BASE = 256 // The number of characters in the alphabet const MOD = 997 // A prime number used for the hash function function rabinKarpSearch(text, pattern) { const patternLength = pattern.length const textLength = text.length const hashPattern = hash(pattern, patternLength) const hashText = [] const indices = [] // Calculate the hash of the first substring in the text hashText[0] = hash(text, patternLength) // Precompute BASE^(patternLength-1) % MOD const basePow = Math.pow(BASE, patternLength - 1) % MOD for (let i = 1; i <= textLength - patternLength + 1; i++) { // Update the rolling hash by removing the first character // and adding the next character in the text hashText[i] = (BASE * (hashText[i - 1] - text.charCodeAt(i - 1) * basePow) + text.charCodeAt(i + patternLength - 1)) % MOD // In case of hash collision, check character by character if (hashText[i] < 0) { hashText[i] += MOD } // Check if the hashes match and perform a character-wise comparison if (hashText[i] === hashPattern) { if (text.substring(i, i + patternLength) === pattern) { indices.push(i) // Store the index where the pattern is found } } } return indices } function hash(str, length) { let hashValue = 0 for (let i = 0; i < length; i++) { hashValue = (hashValue * BASE + str.charCodeAt(i)) % MOD } return hashValue } export { rabinKarpSearch } |
| You are visitor 01402520 — 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. |