如何用JavaScript编写O(n)时间复杂度的子串出现次数统计代码？

你提供的朴素搜索算法时间复杂度为O(n*m)（n是长字符串长度，m是子串长度），在处理较长字符串时效率偏低。下面是基于KMP算法实现的代码，整体时间复杂度为O(n+m)，符合你要求的线性时间（O(n)）需求：

实现思路 #

KMP算法通过预先计算子串的最长前缀后缀数组（LPS），在匹配失败时跳过不必要的字符比较，避免了朴素算法中对长串的频繁回溯，从而将时间复杂度优化到线性级别。

完整代码 #

function kmpSearch(longStr, shortStr) {
    const subLen = shortStr.length;
    const strLen = longStr.length;
    let matchCount = 0;

    // 构建最长前缀后缀数组（LPS）
    function buildLPS(pattern) {
        const lps = new Array(subLen).fill(0);
        let prefixLen = 0;
        let i = 1;

        while (i < subLen) {
            if (pattern[i] === pattern[prefixLen]) {
                prefixLen++;
                lps[i] = prefixLen;
                i++;
            } else {
                if (prefixLen !== 0) {
                    prefixLen = lps[prefixLen - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    const lps = buildLPS(shortStr);
    let strPtr = 0; // 长串遍历指针
    let subPtr = 0; // 子串遍历指针

    while (strPtr < strLen) {
        if (shortStr[subPtr] === longStr[strPtr]) {
            strPtr++;
            subPtr++;
        }

        if (subPtr === subLen) {
            // 找到一次匹配，计数加1
            matchCount++;
            // 利用LPS数组调整子串指针，寻找下一次可能的匹配
            subPtr = lps[subPtr - 1];
        } else if (strPtr < strLen && shortStr[subPtr] !== longStr[strPtr]) {
            // 匹配失败时调整子串指针
            if (subPtr !== 0) {
                subPtr = lps[subPtr - 1];
            } else {
                strPtr++;
            }
        }
    }

    return matchCount;
}

// 测试示例
console.log(kmpSearch("lorielol loled", "lol")); // 输出：2

关键细节说明 #

• LPS数组的作用：它记录了子串中每个位置对应的最长相等前缀和后缀的长度，当匹配失败时，我们可以根据这个值直接将子串指针移动到合适的位置，无需回溯长串指针，大幅减少了比较次数。
• 时间复杂度分析：构建LPS数组的时间是O(m)，遍历长串的时间是O(n)，整体时间复杂度为O(n+m)，属于线性时间范畴，相比朴素搜索的O(n*m)效率提升显著。

内容的提问来源于stack exchange，提问作者Wisten