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/String/ZFunction.js at master · ex1234/JavaScript Expand file tree/ Copy pathZFunction.jsMore file actions 41 lines (37 loc) · 1.54 KB / Copy pathZFunction.jsFile metadata and controls41 lines (37 loc) · 1.54 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 /** * @author: Adrito Mukherjee * Implementation of ZFunction in JavaScript * ZFunction at an index i gives the length of the longest substring starting at i, that is also a prefix of the whole string * ZFunction for all indices in a string can be calculated in O(N) * @see https://cp-algorithms.com/string/z-function.html * @param {String} text The string whose Z Function is to be calculated * @return {Array} Returns an array whose i-th index is the value of Z Function for text at index i */ function zFunction(text) { const length = text.length const zArray = Array(length).fill(0) // Initializing left and right variable to zero let left = 0 let right = 0 for (let index = 0; index < length; index++) { // If index is less than or equal to right, we reuse the values of zFunction at index right-index+1 // It is made sure that value of zFunction at index is not greater than maximum possible value at index if (index <= right) { zArray[index] = Math.min(right - index + 1, zArray[index - left]) } // After zArray[index] is initialized, we see if we can increase its value by trivially comparing character by character while ( index + zArray[index] < length && text[zArray[index]] === text[index + zArray[index]] ) { zArray[index]++ } // If index + zArray[index] - 1 is greater than right, we update values of variables left and right if (index + zArray[index] - 1 > right) { left = index right = index + zArray[index] - 1 } } return zArray } export default zFunction |
| 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. |