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算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!