C++ KMP算法实现

1、先求 next 数组：

// pattern 是模式串，n 是串长度
void kmpnext(string pattern, int next[], int n) {
    next[0] = -1;
    int k = -1;
    int j = 1;

    while(j < n) {
        if(pattern[j-1] == pattern[k] || k == -1) {// 这个 k 指的是上一轮的 next 值，即 next[j-1]
            next[j++] = ++k;
        }
        else { // 这里 k 会递归找 j - 1 的 next 值 的 next 值......，直到进入上面那个 if 中
            k = next[k];
        }
    }
}

2、利用 next 数组进行 KMP 算法匹配：

// text 是原串，pattern 是模式串，tL 是原串长度，pL 是模式串长度
int kmp(string text, string pattern, int tL, int pL, int next[]) {
    int i = 0, j = 0;
    while(i < tL && j < pL) {
        if(text[i] == pattern[j]) { // 如果相等，两个一起后移
            i++;
            j++;
        }
        else if(j != 0){            // 如果不相等且非模式串第一个字符，i 不动，j 找 next
            j = next[j];
        }
        else {                      // 如果不相等且是模式串第一个字符，i 后移
            i++;
        }
    }
    if(j == pL) {                   // 如果 j 走到最后，说明模式串每个字符都匹配过
        return i - pL;
    }
    return -1;
}

3、测试

int main()
{

    string text = "ACBABE";
    string pattern = "BE";
    int tL = text.length();
    int pL = pattern.length();
    int next[pL];
    kmpnext(pattern, next, pL);
    for(int i = 0; i < pL; i++) // 打印 next 数组
        cout << next[i] << " ";
    cout << endl;
    cout << "index = " << kmp(text, pattern, tL, pL, next);
    return 0;
}

捕获.PNG