做注册任务的网站有哪些,seo搜索排名优化,沈阳企业网站排名优化,搬瓦工wordpress建站字符串匹配算法
字符串匹配算法是在一个字符串#xff08;称为文本#xff09;中查找另一个字符串#xff08;称为模式#xff09;出现的位置或者是否存在的算法。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法和Rabin-Karp算法。下面是对这些算法的简要介…字符串匹配算法
字符串匹配算法是在一个字符串称为文本中查找另一个字符串称为模式出现的位置或者是否存在的算法。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法和Rabin-Karp算法。下面是对这些算法的简要介绍 暴力匹配Brute Force算法
算法原理暴力匹配算法是最简单的一种字符串匹配算法。它的原理是从文本的每一个可能的位置开始依次比较文本中的子串与模式串是否匹配。如果匹配成功则返回匹配的位置否则继续尝试下一个位置。时间复杂度平均情况下为O(m*n)其中m为文本长度n为模式长度。优点 算法简单易懂容易实现。不需要额外的预处理步骤。缺点 效率较低时间复杂度为O(m*n)其中m为文本长度n为模式长度。对于大规模文本和模式性能较差。
代码示例
/*** 暴力匹配算法** param text 目标文本* param pattern 匹配模式* returns 返回匹配模式在目标文本中的起始位置如果没有找到匹配则返回-1*/
function bruteForce(text, pattern) {const m text.length;const n pattern.length;// 遍历文本串查找模式串for (let i 0; i m - n; i) {let j 0;// 逐个比较文本串和模式串的字符while (j n text[i j] pattern[j]) {j;}// 如果模式串全部匹配成功if (j n) {return i; // 返回匹配的起始位置}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text hello world;
const pattern world;
console.log(bruteForce(text, pattern)); // 输出: 6KMPKnuth-Morris-Pratt算法
算法原理KMP算法通过预处理模式串构建部分匹配表也称为next数组然后在匹配过程中根据部分匹配表来移动模式串避免重复比较已经匹配的部分。时间复杂度O(mn)其中m为文本长度n为模式长度。优点 在大多数情况下时间复杂度为O(mn)具有较高的效率。通过部分匹配表避免了不必要的比较提高了搜索速度。缺点 实现较为复杂需要构建部分匹配表。在特定情况下性能可能不如其他算法。
代码示例
/*** 生成KMP算法中的部分匹配表** param pattern 待匹配的字符串* returns 返回部分匹配表*/
function kmpTable(pattern) {// 获取模式串的长度const n pattern.length;// 初始化表数组初始值都为0const table new Array(n).fill(0);// 初始化指针i和jlet i 1, j 0;// 当i小于n时循环执行以下操作while (i n) {// 如果模式串的第i个字符与第j个字符相等if (pattern[i] pattern[j]) {// j指针向后移动一位j;// 将j的值赋给表数组的第i个位置table[i] j;// i指针向后移动一位i;// 如果j大于0} else if (j 0) {// 将j的值更新为表数组的第j-1个位置的值j table[j - 1];// 如果j等于0} else {// i指针向后移动一位i;}}// 返回表数组return table;
}/*** 使用KMP算法在文本中搜索模式串** param text 文本* param pattern 模式串* returns 返回模式串在文本中的起始位置如果未找到则返回-1*/
function kmpSearch(text, pattern) {const m text.length;const n pattern.length;if (n 0) {return 0;}// 生成部分匹配表const table kmpTable(pattern);let i 0, j 0;while (i m) {// 如果当前字符匹配成功if (text[i] pattern[j]) {i;j;// 如果已经匹配完整个模式串if (j n) {return i - n; // 返回匹配的起始位置}// 如果当前字符匹配失败且模式串的下一个字符不是第一个字符} else if (j 0) {// 根据部分匹配表进行跳转j table[j - 1];// 如果当前字符匹配失败且模式串的下一个字符是第一个字符} else {i;}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text hello world;
const pattern world;
console.log(kmpSearch(text, pattern)); // 输出: 6Boyer-Moore算法
算法原理Boyer-Moore算法是一种启发式的字符串匹配算法它利用了模式串中的信息来尽可能地跳过不必要的比较。主要有两种启发式规则坏字符规则和好后缀规则。时间复杂度最坏情况下为O(m*n)但平均情况下具有较高的效率。优点 在实际应用中通常具有较高的效率尤其是在模式串较长、字符集较大的情况下。利用了启发式规则能够快速跳过不匹配的位置减少比较次数。缺点 实现相对复杂需要理解和实现坏字符规则和好后缀规则。在某些情况下性能可能不如其他算法。
代码示例
/*** Boyer-Moore 字符串匹配算法** param text 待匹配的文本* param pattern 待匹配的模式* returns 返回匹配到的起始位置若未找到则返回-1*/
function boyerMoore(text, pattern) {const m text.length;const n pattern.length;if (n 0) {return 0;}// 构建字符最后出现位置的映射const skip {};for (let i 0; i n - 1; i) {skip[pattern[i]] n - i - 1;}skip[pattern[n - 1]] n;let i 0;while (i m - n) {let j n - 1;// 从后往前匹配文本和模式while (j 0 text[i j] pattern[j]) {j--;}if (j -1) {return i; // 如果全部匹配成功返回匹配的起始位置}// 根据字符最后出现位置的映射计算下一个匹配位置i skip[text[i n - 1]] || n;}return -1; // 没有找到匹配
}// 示例用法
const text hello world;
const pattern world;
console.log(boyerMoore(text, pattern)); // 输出: 6Rabin-Karp算法
算法原理Rabin-Karp算法利用哈希函数来对模式串和文本中的子串进行哈希计算然后比较哈希值来确定是否匹配。它适用于在一段文本中搜索多个不同的模式串。时间复杂度平均情况下为O(mn)其中m为文本长度n为模式长度。优点 在多个模式串匹配和字符串搜索中具有良好的性能。利用哈希函数实现了快速的模式匹配。缺点 对于哈希冲突的处理和哈希函数的设计需要注意影响算法的准确性和性能。在某些情况下哈希函数的计算可能会造成额外的开销。
代码示例
/*** Rabin-Karp 字符串匹配算法** param text 文本字符串* param pattern 模式字符串* returns 返回模式字符串在文本字符串中首次出现的位置若未找到则返回 -1*/
function rabinKarp(text, pattern) {const m text.length;const n pattern.length;if (n 0) {return 0;}// 字符集大小const d 256; // 字符集大小// 一个质数const q 101; // 一个质数let p 0, t 0, h 1;// 计算哈希值的基础值for (let i 0; i n - 1; i) {h (h * d) % q;}// 计算模式串和文本串的哈希值for (let i 0; i n; i) {p (d * p pattern.charCodeAt(i)) % q;t (d * t text.charCodeAt(i)) % q;}// 遍历文本串查找匹配for (let i 0; i m - n; i) {// 哈希值相等且字符串相等时返回匹配的起始位置if (p t text.substring(i, i n) pattern) {return i; // 返回匹配的起始位置}// 更新文本串的哈希值if (i m - n) {t (d * (t - text.charCodeAt(i) * h) text.charCodeAt(i n)) % q;if (t 0) {t q;}}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text hello world;
const pattern world;
console.log(rabinKarp(text, pattern)); // 输出: 6
