KMP算法

KMP（Knuth-Morris-Pratt）算法是一种经典的字符串匹配算法，用于在一个主串中快速查找一个模式串（子串）是否出现过，并返回其位置。它的时间复杂度是 O(n + m)，其中 n 是主串长度，mmm 是模式串长度。

KMP的核心思想

构建一个next 数组（前缀函数），当模式串的某个位置匹配失败时，我们可以利用已经匹配的信息，将模式串向右移动，不用重新从头比较。

如何构建next数组？

i	0	1	2	3	4	5
ch	a	b	a	b	c	a
next	0	0	1	2	0	1

vector<int> buildNext(const string& pattern) 
{
    int m = pattern.size();
    vector<int> next(m, 0);
    int j = 0; // 前缀末尾指针

    for (int i = 1; i < m; i++) 
{
        while (j > 0 && pattern[i] != pattern[j])
            j = next[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        next[i] = j;
    }
    return next;
}

int KMP(string text, string pattern) 
{
    int n = text.size(), m = pattern.size();
    vector<int> next(m);

    // 构建next数组
    for(int i = 1, j = 0; i < m; i++)
    {
        while(j > 0 && pattern[i] != pattern[j])
        {
            j = next[j - 1];
        }
        if(pattern[i] == pattern[j]) j++;
        next[i] = j;
    }

    // KMP匹配
    for(int i = 0, j = 0; i < n; i++)
    {
        while(j > 0 && text[i] != pattern[j])
        {
            j = next[j - 1];
        }
        if(text[i] == pattern[j]) j++;
        if(j == m) return i - j + 1;
    }
    
    return -1;
}