KMP字符串匹配算法

一种高效的字符串匹配算法，通过预处理模式串，避免了不必要的回溯，提升了匹配效率。它的时间复杂度是 O(n + m)，其中 n 是文本串的长度，m 是模式串的长度。

在前端开发中，KMP算法常用于需要在大量文本中快速查找特定模式的场景。

搜索功能

KMP算法非常适合用于实现高效的搜索功能。例如，在搜索引擎中，用户输入关键词时，搜索引擎需要快速地从文档或网页内容中查找匹配的关键词。KMP算法能确保在大量文本中迅速找到匹配项，避免了暴力匹配的低效回溯。

🔶搜索框：在网站或应用的搜索框中，用户输入搜索关键词时，实时匹配并高亮显示结果。

🔶代码搜索工具：在代码编辑器或集成开发环境（IDE）中，可以使用KMP算法来快速匹配函数、变量名等。

const text = "hello world, welcome to KMP search";
const pattern = "KMP";
const result = kmp(text, pattern);
console.log(result); // 输出：22，表示模式串 "KMP" 在文本串中的起始位置

文本高亮

在文本编辑器或浏览器中，当用户输入关键字时，可以实时对文本进行高亮显示。使用KMP算法可以快速找到文本中所有的匹配项，然后将它们高亮显示。

🔶代码编辑器：在IDE中，用户可以通过输入关键字，实时高亮显示文件中所有的匹配项。

🔶网页文本搜索：用户在网页上查找特定的内容时，网页上的所有匹配内容都可以被高亮显示。

const text = "This is a test text. Let's test KMP matching.";
const pattern = "test";
let index = kmp(text, pattern);
while (index !== -1) {
    console.log(`Found "test" at index ${index}`);
    index = kmp(text.substring(index + 1), pattern);
}

数据过滤

在处理大规模数据时，KMP算法可以用来过滤特定的字符串模式。例如，日志系统、监控系统、社交媒体内容过滤等，都需要快速定位特定的文本模式，KMP算法能够大大提高匹配效率。

🔶日志系统：实时分析日志内容，查找异常模式或错误信息。

🔶敏感词过滤：在社交媒体平台或聊天应用中，检测并屏蔽敏感词或不良内容。

🔶数据清洗：在处理大规模文本数据时，使用KMP算法来匹配和过滤特定的模式或内容。

const logs = [
    "2025-03-20 10:00: Error: failed to connect",
    "2025-03-20 10:05: Warning: low disk space",
    "2025-03-20 10:10: Error: timeout occurred"
];
const errorPattern = "Error";
logs.forEach((log, index) => {
    if (kmp(log, errorPattern) !== -1) {
        console.log(`Log ${index} contains an error: ${log}`);
    }
});

文本匹配和替换

KMP算法可以用于文本编辑和替换。例如，在一个文本编辑器中，用户希望替换文中的特定模式，KMP算法能帮助快速找到所有匹配的位置，避免重复遍历文本。

🔶文本编辑器：在文本编辑器中查找并替换指定的内容。

🔶批量文本替换：在处理文件时，使用KMP算法快速定位匹配内容，并替换为新的内容。

const text = "I love programming. Programming is fun.";
const pattern = "Programming";
const replacement = "Coding";

let index = kmp(text, pattern);
let modifiedText = text;
while (index !== -1) {
    modifiedText = modifiedText.substring(0, index) + replacement + modifiedText.substring(index + pattern.length);
    index = kmp(modifiedText.substring(index + replacement.length), pattern);
}
console.log(modifiedText); // 输出：I love programming. Coding is fun.

网页爬虫

在网页爬虫应用中，需要分析HTML页面，并从中提取特定的内容（例如链接、标题、元数据等）。使用KMP算法可以高效地查找页面中的模式，以便快速提取需要的内容。

🔶网页数据提取：从网页中提取特定信息，如链接、标题、文章内容等。 🔶内容分析：分析网页中大量文本数据，快速定位有价值的信息。

const htmlContent = "<html><head><title>Sample Webpage</title></head><body>Content goes here.</body></html>";
const pattern = "<title>";
const endPattern = "</title>";

let startIndex = kmp(htmlContent, pattern);
let endIndex = kmp(htmlContent, endPattern);
const title = htmlContent.substring(startIndex + pattern.length, endIndex);
console.log(title); // 输出：Sample Webpage

KMP算法主要应用于需要高效进行字符串匹配的场景，在前端开发中常见的应用包括：文本搜索、高亮显示、数据过滤、文本替换、网页爬虫等。由于KMP算法能够避免不必要的回溯，它对于处理大量数据时的效率提升非常显著。

KMP字符串匹配算法 ​

搜索功能 ​

文本高亮 ​

数据过滤 ​

文本匹配和替换 ​