KMP算法(java实现）_kmp算法 java

kmp算法是一种改进的字符串匹配方法，该算法的核心是利用字符串匹配失败后的可用信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

什么是“字符串匹配失败”？

首先，我们先要了解kmp主要的匹配机制——kmp的匹配机制是在BF算法上进行优化的，那么，什么是BF算法呢？
BF（brute force）算法就是字符串的暴力匹配法：对主串的每个字符进行一一匹配，匹配的方式也是逐字符进行检查

 public boolean BF(String query,String target){
   
        for(int i=0;i<query.length();i++){
   
            int start=i;
            int ptr=0;
            while (ptr < target.length()) {
   
                if(query.charAt(start+ptr)!=target.charAt(ptr))
                    break;
                p
1
2
3
4
5
6
7
8
9
10