如何以O(N)时间复杂度查找子串在母串中的所有起始索引？KMP可行吗？

问题说明 #

给定模式串str1和文本串str2，需要找出str2中所有str1出现的起始索引。比如输入str1="abc"、str2="abckdabcgfacabc"，输出应为[0,5,12]。

原实现的问题 #

你提供的代码依赖indexOf()方法，每次调用都会在子串中从头匹配，最坏情况下时间复杂度会达到O(N*M)（N是文本串长度，M是模式串长度），效率不够理想。

用KMP算法实现线性时间匹配 #

当然可以用KMP算法实现，它的时间复杂度是O(N+M)，核心是通过预处理模式串生成前缀函数数组（也叫部分匹配表），避免匹配失败时文本串指针回溯，大幅提升效率。

实现步骤 #

1. 计算前缀函数数组：遍历模式串，对每个位置计算最长相等前缀后缀的长度，这个数组用于匹配失败时快速调整模式串的匹配位置。
2. KMP匹配过程：用两个指针分别遍历文本串和模式串，匹配成功则同时移动指针；匹配失败时，利用前缀函数数组调整模式串指针，无需回溯文本串指针，直到找到所有匹配的起始索引。

完整Java代码实现 #

import java.util.ArrayList;
import java.util.List;

public class KMPMatcher {
    public static List<Integer> findAllMatchingIndexes(String pattern, String text) {
        List<Integer> result = new ArrayList<>();
        if (pattern.isEmpty() || text.isEmpty() || pattern.length() > text.length()) {
            return result;
        }

        // 第一步：计算前缀函数数组（部分匹配表）
        int[] prefix = computePrefixFunction(pattern);
        int patternLen = pattern.length();
        int textLen = text.length();
        int j = 0; // 模式串的指针

        // 第二步：遍历文本串进行匹配
        for (int i = 0; i < textLen; i++) {
            // 匹配失败时，根据前缀函数回退模式串指针
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = prefix[j - 1];
            }
            // 匹配成功，同时移动两个指针
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            // 找到完整匹配，记录起始索引
            if (j == patternLen) {
                result.add(i - patternLen + 1);
                // 利用前缀函数回退，继续寻找下一个匹配
                j = prefix[j - 1];
            }
        }
        return result;
    }

    private static int[] computePrefixFunction(String pattern) {
        int len = pattern.length();
        int[] prefix = new int[len];
        int j = 0; // 前缀的长度

        for (int i = 1; i < len; i++) {
            // 当前字符不匹配，回退j
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = prefix[j - 1];
            }
            // 当前字符匹配，前缀长度加1
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
                prefix[i] = j;
            } else {
                prefix[i] = 0;
            }
        }
        return prefix;
    }

    // 测试示例
    public static void main(String[] args) {
        String str1 = "abc";
        String str2 = "abckdabcgfacabc";
        List<Integer> indexes = findAllMatchingIndexes(str1, str2);
        System.out.println(indexes); // 输出 [0, 5, 12]
    }
}

代码说明 #

• computePrefixFunction方法：生成模式串的前缀函数数组，比如模式串"abcabc"的前缀数组是[0,0,0,1,2,3]，表示每个位置的最长相等前缀后缀长度。
• findAllMatchingIndexes方法：通过双指针遍历文本串和模式串，匹配成功时记录起始索引，然后利用前缀函数回退模式串指针，继续寻找下一个匹配，无需重置文本串指针，保证了线性时间复杂度。

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