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

Commit5bdcbb3

Browse files
committed
Code style fixes.
1 parent9e210ae commit5bdcbb3

File tree

3 files changed

+43
-19
lines changed

3 files changed

+43
-19
lines changed

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,8 @@ a set of rules that precisely define a sequence of operations.
7272
***Strings**
7373
*`A`[Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences
7474
*`B`[Hamming Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - number of positions at which the symbols are different
75-
*`A`[Knuth–Morris–Pratt Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) (KMP Algorithm) - substring search
75+
*`A`[Knuth–Morris–Pratt Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) (KMP Algorithm) - substring search (pattern matching)
76+
*`A`[Z Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/z-algorithm) - substring search (pattern matching)
7677
*`A`[Rabin Karp Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - substring search
7778
*`A`[Longest Common Substring](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring)
7879
***Searches**
Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,16 @@
11
importzAlgorithmfrom'../zAlgorithm';
22

33
describe('zAlgorithm',()=>{
4-
it('should find word position in given text',()=>{
5-
expect(zAlgorithm('abcbcglx','abca')).toBe(-1);
6-
expect(zAlgorithm('abcbcglx','bcgl')).toBe(3);
7-
expect(zAlgorithm('abcxabcdabxabcdabcdabcy','abcdabcy')).toBe(15);
8-
expect(zAlgorithm('abcxabcdabxabcdabcdabcy','abcdabca')).toBe(-1);
9-
expect(zAlgorithm('abcxabcdabxaabcdabcabcdabcdabcy','abcdabca')).toBe(12);
10-
expect(zAlgorithm('abcxabcdabxaabaabaaaabcdabcdabcy','aabaabaaa')).toBe(11);
4+
it('should find word positions in given text',()=>{
5+
expect(zAlgorithm('abcbcglx','abca')).toEqual([]);
6+
expect(zAlgorithm('abca','abca')).toEqual([0]);
7+
expect(zAlgorithm('abca','abcadfd')).toEqual([]);
8+
expect(zAlgorithm('abcbcglabcx','abc')).toEqual([0,7]);
9+
expect(zAlgorithm('abcbcglx','bcgl')).toEqual([3]);
10+
expect(zAlgorithm('abcbcglx','cglx')).toEqual([4]);
11+
expect(zAlgorithm('abcxabcdabxabcdabcdabcy','abcdabcy')).toEqual([15]);
12+
expect(zAlgorithm('abcxabcdabxabcdabcdabcy','abcdabca')).toEqual([]);
13+
expect(zAlgorithm('abcxabcdabxaabcdabcabcdabcdabcy','abcdabca')).toEqual([12]);
14+
expect(zAlgorithm('abcxabcdabxaabaabaaaabcdabcdabcy','aabaabaaa')).toEqual([11]);
1115
});
1216
});

‎src/algorithms/string/z-algorithm/zAlgorithm.js

Lines changed: 30 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,13 @@
1+
// The string separator that is being used for "word" and "text" concatenation.
2+
constSEPARATOR='$';
3+
14
/**
2-
*@param {string} word
3-
*@param {string} text
5+
*@param {string} zString
46
*@return {number[]}
57
*/
6-
7-
functionbuildZArray(word,text){
8-
constzString=`${word}$${text}`;
8+
functionbuildZArray(zString){
99
constzArray=newArray(zString.length);
10+
1011
letleft=0;
1112
letright=0;
1213
letk=0;
@@ -44,14 +45,32 @@ function buildZArray(word, text) {
4445
/**
4546
*@param {string} text
4647
*@param {string} word
47-
*@return {number}
48+
*@return {number[]}
4849
*/
4950
exportdefaultfunctionzAlgorithm(text,word){
50-
constzArray=buildZArray(word,text);
51-
for(leti=1;i<zArray.length;i+=1){
52-
if(zArray[i]===word.length){
53-
return(i-word.length-1);
51+
// The list of word's positions in text. Word may be found in the same text
52+
// in several different positions. Thus it is an array.
53+
constwordPositions=[];
54+
55+
// Concatenate word and string. Word will be a prefix to a string.
56+
constzString=`${word}${SEPARATOR}${text}`;
57+
58+
// Generate Z-array for concatenated string.
59+
constzArray=buildZArray(zString);
60+
61+
// Based on Z-array properties each cell will tell us the length of the match between
62+
// the string prefix and current sub-text. Thus we're may find all positions in zArray
63+
// with the number that equals to the length of the word (zString prefix) and based on
64+
// that positions we'll be able to calculate word positions in text.
65+
for(letcharIndex=1;charIndex<zArray.length;charIndex+=1){
66+
if(zArray[charIndex]===word.length){
67+
// Since we did concatenation to form zString we need to subtract prefix
68+
// and separator lengths.
69+
constwordPosition=charIndex-word.length-SEPARATOR.length;
70+
wordPositions.push(wordPosition);
5471
}
5572
}
56-
return-1;
73+
74+
// Return the list of word positions.
75+
returnwordPositions;
5776
}

0 commit comments

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