Java教程

kmp算法

本文主要是介绍kmp算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

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

数据范围：

1 \le len(S) \le 5*10^5, 1 \le len(T) \le 10^61≤len(S)≤5∗105,1≤len(T)≤106

复杂度要求：

O(n \cdot m) \O(n⋅m) 

示例1

输入：

"ababab","abababab"

复制返回值：

2

复制

示例2

输入：

"abab","abacabab"

复制返回值：

1
public int kmp (String S, String T) {
    int length = S.length();
    int i = T.length()-length;
    int count = 0;
    while(i>=0){
        String temp = T.substring(i,length+i);
        if(temp.equals(S)){
            count++;
        }
        i--;
    }
    return count;
}

这篇关于kmp算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航