JavaScript中实现输入字符串含目标子串的部分匹配方法咨询

针对你需要检测输入字符串是否包含目标字符串的连续部分子串（而非完整匹配）的需求，以下是几种实用的实现方案：

一、修改KMP算法实现高效部分匹配 #

你现有的KMP算法是用于完整字符串匹配的，只需稍作修改，就能在匹配过程中达到指定最小长度时立即返回结果，无需等待完整匹配完成。这种方法保持了KMP算法O(n+m)的高效时间复杂度，适合长文本场景。

var makeKMPTable = function(word) {
    if(Object.prototype.toString.call(word) == '[object String]' ) {
        word = word.split('');
    }
    var results = [];
    var pos = 2;
    var cnd = 0;

    results[0] = -1;
    results[1] = 0;
    while (pos < word.length) {
        if (word[pos - 1] == word[cnd]) {
            cnd++;
            results[pos] = cnd;
            pos++;
        } else if (cnd > 0) {
            cnd = results[cnd];
        } else {
            results[pos] = 0;
            pos++;
        }
    }
    return results;
};

// 适配部分匹配的KMP搜索函数，支持指定最小匹配长度
var KMPPartialSearch = function(string, word, minMatchLength = 1) {
    if(Object.prototype.toString.call(string) == '[object String]' ) {
        string = string.split('');
    }
    if(Object.prototype.toString.call(word) == '[object String]' ) {
        word = word.split('');
    }

    if (minMatchLength < 1 || minMatchLength > word.length) return false;
    
    var m = 0;
    var i = 0;
    var T = makeKMPTable(word);

    while (m + i < string.length) {
        if (word[i] == string[m + i]) {
            i++;
            // 匹配长度达到设定阈值时直接返回true
            if (i >= minMatchLength) {
                return true;
            }
        } else {
            m = m + i - T[i];
            if (T[i] > -1) {
                i = T[i];
            } else {
                i = 0;
            }
        }
    }
    return false;
};

// 测试你的示例
console.log(KMPPartialSearch("sssrtAnimyt5678", "Animation", 4)); // 返回true

二、滑动窗口暴力匹配（简单直观） #

如果目标字符串长度较短，直接遍历目标的所有符合长度要求的连续子串，再检查输入字符串是否包含该子串即可。这种方法实现简单，适合小体量文本场景。

function hasPartialMatch(input, target, minLen = 1) {
    if (minLen < 1 || minLen > target.length) return false;
    // 遍历目标所有长度≥minLen的连续子串
    for (let i = 0; i <= target.length - minLen; i++) {
        const subStr = target.slice(i, i + minLen);
        if (input.includes(subStr)) {
            return true;
        }
    }
    return false;
}

// 测试示例
console.log(hasPartialMatch("sssrtAnimyt5678", "Animation", 4)); // 返回true

三、正则表达式实现（代码简洁） #

通过动态生成包含目标所有符合要求子串的正则表达式，快速检测匹配情况。注意需要转义正则特殊字符，避免匹配异常。

function hasPartialMatchRegex(input, target, minLen = 1) {
    if (minLen < 1 || minLen > target.length) return false;
    const subStrs = [];
    // 生成所有符合长度要求的子串并转义特殊字符
    for (let i = 0; i <= target.length - minLen; i++) {
        const escapedSub = target.slice(i, i + minLen).replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
        subStrs.push(escapedSub);
    }
    const matchRegex = new RegExp(subStrs.join('|'));
    return matchRegex.test(input);
}

// 测试示例
console.log(hasPartialMatchRegex("sssrtAnimyt5678", "Animation", 4)); // 返回true

额外优化方向 #

如果你的需求仅需匹配目标字符串的前缀子串（比如示例中的"Anim"是"Animation"的前缀），可以进一步简化逻辑，只需检查输入是否包含目标的任意长度≥阈值的前缀：

function hasPrefixPartialMatch(input, target, minLen = 1) {
    if (minLen < 1 || minLen > target.length) return false;
    for (let len = minLen; len <= target.length; len++) {
        const prefix = target.slice(0, len);
        if (input.includes(prefix)) {
            return true;
        }
    }
    return false;
}

内容的提问来源于stack exchange，提问作者Abhilash D K