mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 00:01:37 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
84 lines
2.9 KiB
JavaScript
84 lines
2.9 KiB
JavaScript
/*
|
|
* 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')
|