kmp算法

[编程题]kmp算法

热度指数：33411 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次

数据范围： $1 \le len(S) \le 500000, 1 \le len(T) \le 1000000$

要求：空间复杂度 $O(len(S))$ ，时间复杂度 $O(len(S)+len(T))$

示例1

输入

"ababab","abababab"

输出

示例2

输入

"abab","abacabab"

输出

算法知识视频讲解

JavaScript Node

极品光头强

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
function kmp( S ,  T ) {
    var index = T.indexOf(S);
    var count = 0;
    while(index > -1) {
        count++;
        index = T.indexOf(S, index + 1);
    }
    return count;
    
}
module.exports = {
    kmp : kmp
};

发表于 2023-10-18 21:06:59 回复(0)