Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7fb1215

Browse files
authored
algorithm: ZFunction (TheAlgorithms#1239)
* algorithm: ZFunction* made requested changes* corrected spelling mistakes* made requested changes
1 parentcc0700f commit7fb1215

File tree

2 files changed

+49
-0
lines changed

2 files changed

+49
-0
lines changed

‎String/ZFunction.js

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/**
2+
*@author: Adrito Mukherjee
3+
* Implementation of ZFunction in JavaScript
4+
* ZFunction at an index i gives the length of the longest substring starting at i, that is also a prefix of the whole string
5+
* ZFunction for all indices in a string can be calculated in O(N)
6+
*@see https://cp-algorithms.com/string/z-function.html
7+
*@param {String} text The string whose Z Function is to be calculated
8+
*@return {Array} Returns an array whose i-th index is the value of Z Function for text at index i
9+
*/
10+
11+
functionzFunction(text){
12+
constlength=text.length
13+
constzArray=Array(length).fill(0)
14+
// Initializing left and right variable to zero
15+
letleft=0
16+
letright=0
17+
for(letindex=0;index<length;index++){
18+
// If index is less than or equal to right, we reuse the values of zFunction at index right-index+1
19+
// It is made sure that value of zFunction at index is not greater than maximum possible value at index
20+
if(index<=right){
21+
zArray[index]=Math.min(right-index+1,zArray[index-left])
22+
}
23+
24+
// After zArray[index] is initialized, we see if we can increase its value by trivially comparing character by character
25+
while(
26+
index+zArray[index]<length&&
27+
text[zArray[index]]===text[index+zArray[index]]
28+
){
29+
zArray[index]++
30+
}
31+
32+
// If index + zArray[index] - 1 is greater than right, we update values of variables left and right
33+
if(index+zArray[index]-1>right){
34+
left=index
35+
right=index+zArray[index]-1
36+
}
37+
}
38+
returnzArray
39+
}
40+
41+
exportdefaultzFunction

‎String/test/ZFunction.test.js

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
importzFunctionfrom'../ZFunction'
2+
3+
test('Testing zFunction',()=>{
4+
expect(zFunction('aabxaayaab')).toEqual([10,1,0,0,2,1,0,3,1,0])
5+
expect(zFunction('aabxaabxcaabxaabxay')).toEqual([
6+
19,1,0,0,4,1,0,0,0,8,1,0,0,5,1,0,0,1,0
7+
])
8+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp