고급 문자열
트라이(접두사 트리)
class TrieNode {
constructor() {
this.children = {};
this.endOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let cur = this.root;
for (let i = 0; i < word.length; i += 1) {
const ch = word.charAt(i);
let node = cur.children[ch];
if (!node) {
node = new TrieNode();
cur.children[ch] = node;
}
cur = node;
}
cur.endOfWord = true;
}
search(word) {
let cur = this.root;
for (let i = 0; i < word.length; i += 1) {
const ch = word.charAt(i);
const node = cur.children[ch];
if (!node) return false;
cur = node;
}
return cur.endOfWord;
}
delete(word) {
const deleteRecursively = (cur, index) => {
if (index === word.length) {
if (!cur.endOfWord) return false;
cur.endOfWord = false;
return Object.keys(cur.children).length === 0;
}
const ch = word.charAt(index);
const node = cur.children[ch];
if (!node) return false;
const shouldDeleteCurrentNode = deleteRecursively(node, index + 1);
if (shouldDeleteCurrentNode) {
delete cur.children[cur];
return Object.keys(cur.children).length === 0;
}
return false;
};
deleteRecursively(this.root, 0);
}
}
보이어-무어 문자열 검색
function buildBadMatchTable(str) {
const tableObj = {};
const strLength = str.length;
for (let i = 0; i < strLength - 1; i += 1) {
tableObj[str[i]] = strLength - 1 - i;
}
if (tableObj[str[strLength - 1]] === undefined) {
tableObj[str[strLength - 1]] = strLength;
}
return tableObj;
}
function boyermoore(str, pattern) {
const badMatchTable = buildBadMatchTable(pattern);
const patternLastIndex = pattern.length - 1;
const maxOffset = str.length - pattern.length;
let offset = 0;
let scanIndex = patternLastIndex;
while (offset <= maxOffset) {
scanIndex = 0;
while (pattern[scanIndex] === str[scanIndex + offset]) {
if (scanIndex === patternLastIndex) return offset;
scanIndex += 1;
}
const badMatchString = str[offset + patternLastIndex];
offset += badMatchTable[badMatchString] || 1;
}
return -1;
}
카누스-모리스-플랫 문자열 검색
function longestPrefix(str) {
const prefix = new Array(str.length);
let maxPrefix = 0;
prefix[0] = 0;
for (let i = 1; i < str.length; i += 1) {
while (str.charAt(i) !== str.charAt(maxPrefix) && maxPrefix > 0) {
maxPrefix = prefix[maxPrefix - 1];
}
if (str.charAt(maxPrefix) === str.charAt(i)) {
maxPrefix += 1;
}
prefix[i] = maxPrefix;
}
return prefix;
}
function KMP(str, pattern) {
const prefixTable = longestPrefix(pattern);
let patternIndex = 0;
let strIndex = 0;
while (strIndex < str.length) {
if (str.charAt(strIndex) !== pattern.charAt(patternIndex)) {
if (patternIndex !== 0) patternIndex = prefixTable[patternIndex - 1];
else strIndex += 1;
} else {
strIndex += 1;
pattern += 1;
}
if (patternIndex === pattern.length) return true;
}
return false;
}
라빈 카프 검색
class RabinKarpSearch {
constructor() {
this.prime = 101;
}
rabinkarpFingerprintHash(str, endLength) {
let hashInt = 0;
if (!endLength) endLength = str.length;
for (let i = 0; i < (endLength || str.length); i += 1) {
hashInt += str.charCodeAt(i) * Math.pow(this.prime, i);
}
return hashInt;
}
recalculateHash(str, oldIndex, newIndex, oldHash, patternLength) {
if (!patternLength) patternLength = str.length;
let newHash = oldHash - str.charCodeAt(oldIndex);
newHash = Math.floor(newHash / this.prime);
newHash +=
str.charCodeAt(newIndex) * Math.pow(this.prime, patternLength - 1);
return newHash;
}
strEquals(str1, startIndex1, endIndex1, str2, startIndex2, endIndex2) {
if (endIndex1 - startIndex1 !== endIndex2 - startIndex2) return false;
while (startIndex1 <= endIndex1 && startIndex2 <= endIndex2) {
if (str1[startIndex1] !== str2[startIndex2]) return false;
startIndex1 += 1;
startIndex2 += 1;
}
return true;
}
rabinkarpSearch(str, pattern) {
const strLength = str.length;
const patternLength = pattern.length;
const patternHash = this.rabinkarpFingerprintHash(pattern, patternLength);
let textHash = this.rabinkarpFingerprintHash(str, patternLength);
for (let i = 0; i < strLength - patternLength + 1; i += 1) {
if (
patternHash === textHash &&
this.strEquals(
str,
i,
i + patternLength - 1,
pattern,
0,
patternLength - 1
)
) {
return i;
}
if (i < strLength - patternLength) {
textHash = this.recalculateHash(
str,
i,
i + patternLength,
textHash,
patternLength
);
}
}
return -1;
}
}