算法 - KMP算法(字符串匹配)

本是古典何须时尚 2023-07-03 10:47 13阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]

# 百度的一个图文介绍[http://www.sohu.com/a/336648975\_453160][http_www.sohu.com_a_336648975_453160] #

package Algorithm.kmp;
    
    import java.util.Arrays;
    
    public class KMPViolenceMatch { 
        public static void main(String[] args) { 
            String str1 = "BBC ABCDAB ABCDABCDABDE";
    
            String str2 = "ABCDABD";
    
            int [] next = kmpNext(str2);
            int kmpsearch = kmpsearch(str1, str2, next);
    
            System.out.println("next[] = " + Arrays.toString(next));
            System.out.println("index = " + kmpsearch);
        }
    
        public static int kmpsearch(String str1, String str2,int [] next){ 
            //遍历str1,i指向str1，j指向str2
            for (int i = 0, j = 0; i < str1.length(); i++) { 
                //str1.charAt(i) != str2.charAt(j)，调整j大小
                //回到匹配表的值相同的下一位
                while (j > 0 && str1.charAt(i) != str2.charAt(j)){ 
                    j = next[j - 1];
               }
    
                if (str1.charAt(i) == str2.charAt(j)){ 
                    j++;
                }
                if (j == str2.length()){ 
                    return i - j + 1;
                }
    
            }
            return -1;
        }
        //获取到一个字符串（子串）的部分匹配值表
        public static int[]  kmpNext(String dest){ 
            //创建一个next数组保存部分匹配值
            int [] next = new int[dest.length()];
            //如果只有一个字符的话那么next[0] = 0;
            next[0] = 0;
    
            for (int i = 1, j = 0; i < dest.length(); i++) { 
                //dest.charAt(i) != dest.charAt(j)，我们需要从next[j-1]获取新的j
                //直到我们发现有dest.charAt(i) == dest.charAt(j)退出
                //就是回溯到与下一个匹配值相同的位置，一直没有就是回溯到j = 0
                while (j > 0 && dest.charAt(i) != dest.charAt(j)){ 
                    j = next[j-1];
                }
    
                //这是dest.charAt(i) == dest.charAt(j)时
                //这个条件满足时，部分匹配值就+1
                if (dest.charAt(i) == dest.charAt(j)){ 
                    j++;
                }
                next[i] = j;
            }
            return next;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200205191654557.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020020519180356.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200205213132602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[http_www.sohu.com_a_336648975_453160]: http://www.sohu.com/a/336648975_453160