Skip to content

字典树#

目录#

1. 模板#

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1e5 + 1;

int Next[MAXN] = { 0 };

int getNext(string p, int length)
{
    // 预计算Next，用于在失配的情况下得到j回溯的位置
    Next[0] = 0;
    Next[1] = 0;
    for (int i = 1; i < length; i++) {
        int j = Next[i];
        while (j && p[i] != p[j]) {
            j = Next[j];
        }
        Next[i + 1] = (p[i] == p[j]) ? j + 1 : 0;
        // 可以进行如下优化
        // Next[i + 1] = (p[i] == p[j]) ? j + 1 : Next[j + 1];
    }
    return 0;
}

// 在str中找pattern
int kmp(string str, string pattern)
{
    size_t slen = str.size();
    size_t plen = pattern.size();
    // 预计算Next[]数组
    getNext(pattern, plen);
    size_t j = 0;
    // 匹配str和pattern的每个字符
    for (size_t i = 0; i < slen; i++) {
        // 失配了，用Next[]找j的回溯位置
        while (j && str[i] != pattern[j]) {
            j = Next[j];
        }
        // 当前位置的字符匹配，继续
        if (str[i] == pattern[j]) {
            j++;
        }
        // 完全匹配
        if (j == plen) {
            // 匹配的起点是 i + 1 - plen，末尾是i
            printf("at location = %lu, %c\n", i + 1 - plen, str[i + 1 - plen]);
        }
    }
    return 0;
}

2. 题目#

KMP类题目博客专栏

Back to top