KMP模板

字符串 C++

字数统计: 116阅读时长: 1 min

 2021/04/14   Share

KMP模板

int KMP(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) {
        return 0;
    }

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

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

    return -1;
}

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/04/14/KMP/

发表日期：April 14th 2021, 4:19:34 pm

更新日期：April 28th 2021, 1:45:46 pm

Next Post

C++ 取整
Previous Post

堆与栈

CATALOG

1. KMP模板

