KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，主要用于在一个文本字符串S内查找一个词W的出现位置。这种算法由Donald Knuth、Vaughan Pratt和James H. Morris共同发明，因此得名。它的最大贡献在于避免了回溯中的无谓比较，提高了匹配效率。
在JavaScript中实现KMP算法，核心在于构建部分匹配表（也称为前缀函数或者失败函数）。部分匹配表记录了模式串（targetStr）中每个位置之前的子串中，有多大长度的相同前缀和后缀。这个表用于指导模式串在文本串（sourceStr）中匹配失败时的回退位数，而不是每次失败都从头开始匹配。
部分匹配表的构建过程可以这样理解：对于模式串的每一个位置i（从0开始计数），我们需要计算一个值，表示在模式串的前i+1个字符组成的子串中，最长的相等的前缀后缀的长度。如果最长的前缀后缀长度为0，则将该位置的部分匹配值设为0；否则，设为该前缀后缀的长度。这个过程可以通过双重循环来实现。
在JavaScript中，部分匹配表的实现方法如下：
```javascript
function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for (var i = 0, j = str.length; i < j; i++) {
var newStr = str.substring(0, i + 1);
if (newStr.length == 1) {
partMatch[i] = 0;
} else {
for (var k = 0; k < i; k++) {
prefix[k] = newStr.slice(0, k + 1);
suffix[k] = newStr.slice(-k - 1);
if (prefix[k] == suffix[k]) {
partMatch[i] = prefix[k].length;
}
}
if (!partMatch[i]) {
partMatch[i] = 0;
}
}
}
return partMatch;
}
```
有了这个部分匹配表后，我们就可以实现KMP算法的核心回退逻辑了。当模式串和文本串进行匹配，遇到不匹配的字符时，可以通过查询部分匹配表中的值来决定模式串应该回退到哪个位置继续匹配，而不是从头开始。
在JavaScript中，KMP算法的回退逻辑实现如下：
```javascript
function KMP(sourceStr, targetStr) {
var partMatchValue = kmpGetStrPartMatchValue(targetStr);
var result = false;
for (var i = 0, j = sourceStr.length; i < j; i++) {
for (var m = 0, n = targetStr.length; m < n; m++) {
if (sourceStr.charAt(i + m) == targetStr.charAt(m)) {
if (m == targetStr.length - 1) {
result = true;
break;
}
} else {
if (m > 0 && partMatchValue[m - 1] > 0) {
m = partMatchValue[m - 1] - 1;
} else {
break;
}
}
}
if (result) {
break;
}
}
return result;
}
```
在这个回退算法中，我们通过`kmpGetStrPartMatchValue`函数获得模式串的部分匹配表，然后进行双层循环。外层循环遍历文本串，内层循环遍历模式串。一旦在模式串中找到匹配的字符，我们继续向后匹配；一旦发现不匹配的字符，我们根据部分匹配表决定模式串应该回退到哪个位置。如果找到一个匹配成功的字符，我们就将`result`设为`true`，并跳出内层循环。如果内层循环因为不匹配而退出，则回退外层循环，继续匹配文本串的下一个字符。
为了加深理解，我们可以对上述JavaScript代码进行测试。例如，如果我们有一个文本串`s`和一个模式串`t`，我们可以通过调用`KMP`函数来判断`t`是否为`s`的子串：
```javascript
var s = "BBCABCDABABCDABCDABDE";
var t = "ABCDABD";
console.log(KMP(s, t)); // 输出 true
```
以上就是基于KMP算法在JavaScript中的实现方法。KMP算法因其高效的匹配性能，非常适合处理大规模的文本匹配任务，尤其在一些文本处理、搜索算法中得到广泛应用。对于需要高效字符串匹配功能的开发者而言，掌握KMP算法无疑是一个重要的技能点。
