字符串匹配

问题描述

给定文本串 $T[1...n]$ 和模式串 $P[1...m]$ ，要求找出 $T$ 中所有与 $P$ 相同的子串的起始位置。

KMP算法

算法思想

利用已匹配的信息，避免不必要的比较
构建next数组（失配函数），记录最长相等前后缀
失配时根据next数组回退模式串

时间复杂度

预处理时间： $\mathcal{O}(m)$
匹配时间： $\mathcal{O}(n)$
空间复杂度： $\mathcal{O}(m)$

代码实现

c++
java
python

class Solution {
private:
    vector<int> buildNext(string& pattern) {
        int m = pattern.length();
        vector<int> next(m);
        next[0] = -1;
        int j = -1;
        
        for (int i = 1; i < m; i++) {
            while (j >= 0 && pattern[j + 1] != pattern[i]) {
                j = next[j];
            }
            if (pattern[j + 1] == pattern[i]) j++;
            next[i] = j;
        }
        
        return next;
    }
    
public:
    vector<int> kmpMatch(string& text, string& pattern) {
        vector<int> positions;
        int n = text.length(), m = pattern.length();
        if (m == 0) return positions;
        
        vector<int> next = buildNext(pattern);
        int j = -1;
        
        for (int i = 0; i < n; i++) {
            while (j >= 0 && pattern[j + 1] != text[i]) {
                j = next[j];
            }
            if (pattern[j + 1] == text[i]) j++;
            if (j == m - 1) {
                positions.push_back(i - m + 1);
                j = next[j];
            }
        }
        
        return positions;
    }
};

class Solution {
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        int j = -1;
        
        for (int i = 1; i < m; i++) {
            while (j >= 0 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = next[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) j++;
            next[i] = j;
        }
        
        return next;
    }
    
    public List<Integer> kmpMatch(String text, String pattern) {
        List<Integer> positions = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (m == 0) return positions;
        
        int[] next = buildNext(pattern);
        int j = -1;
        
        for (int i = 0; i < n; i++) {
            while (j >= 0 && pattern.charAt(j + 1) != text.charAt(i)) {
                j = next[j];
            }
            if (pattern.charAt(j + 1) == text.charAt(i)) j++;
            if (j == m - 1) {
                positions.add(i - m + 1);
                j = next[j];
            }
        }
        
        return positions;
    }
}

class Solution:
    def buildNext(self, pattern: str) -> List[int]:
        m = len(pattern)
        next = [0] * m
        next[0] = -1
        j = -1
        
        for i in range(1, m):
            while j >= 0 and pattern[j + 1] != pattern[i]:
                j = next[j]
            if pattern[j + 1] == pattern[i]:
                j += 1
            next[i] = j
        
        return next
    
    def kmpMatch(self, text: str, pattern: str) -> List[int]:
        positions = []
        n, m = len(text), len(pattern)
        if m == 0:
            return positions
        
        next = self.buildNext(pattern)
        j = -1
        
        for i in range(n):
            while j >= 0 and pattern[j + 1] != text[i]:
                j = next[j]
            if pattern[j + 1] == text[i]:
                j += 1
            if j == m - 1:
                positions.append(i - m + 1)
                j = next[j]
        
        return positions