[C++知识库] 【KMP】

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【KMP】 -> 正文阅读

[C++知识库]【KMP】

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010; // N 为匹串长度， M 为模式串长度

int n, m;
int ne[N];
char p[N], s[M]; // p 为匹配串， s 为模式串 

int main(){
    cin >> n >> p + 1 >> m >> s + 1; // 从下标为1开始
    
    // 求 next[] 数组
    // index 1 2 3
    // value 0 0 1
    for ( int i = 2, j = 0; i <= n; i ++ ) {
        while ( j && p[i] != p[j + 1] ) j = ne[j];
        if ( p[i] == p[j + 1] ) j ++;
        ne[i] = j;
    }

    // KMP 模式匹配
    for ( int i = 1, j = 0; i <= m; i ++ ) {
        while ( j && s[i] != p[j + 1] ) j = ne[j];
        if ( s[i] == p[j + 1] ) j ++;
        if (j == n) {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    
    return 0;
}

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {

    if ( haystack == "" && needle == ""){
        return 0;
    }

    let len1 = needle.length; // 匹配串长度
    let len2 = haystack.length; // 模式串长度
    const ne = new Array(len1).fill(0);

    // next[] 数组
    for ( let i = 1, j = 0; i < len1; i ++ ) {
        while ( j > 0 && needle[i] !== needle[j] ) j = ne[j - 1];
        if ( needle[i] == needle[j] ) j ++;
        ne[i] = j;
    }

    // KMP
    for ( let i = 0, j  = 0; i < len2; i ++ ) {
        while ( j > 0 && haystack[i] != needle[j]) j = ne[j - 1];
        if ( haystack[i] == needle[j] ) j ++;

        if (j == len1 ){
            return i - len1 + 1;
        }
    }

    return -1;
};