KMP字符串匹配

柔情只为你懂 2021-09-28 19:40 332阅读 0赞

KMP字符串匹配是一种高效的字符串匹配方法，这种算法大致可分为两个部分，一个是求next数组，另一个是与原串进行匹配比较。

**next数组：**next数组是模式串（pattern）与原串失配后next数组指针（j）应该回溯的位置。

**特点：**与暴力匹配不同的是原串的指针（i）每次与模式串匹配后并不回退，而仅仅回退模式串的指针j并且不总是回退的模式串的第一个元素。

在整个KMP算法中，next数组是最重要的一部分，同时也是较难理解的一部分。

**给定模式串求next数组的方法**

/**
         * 计算next数组的方法
         * @param s 原串
         * @return int[]
         */
        static int[] next(String s) {
           int len = s.length();
           int[] next = new int[len];
           char[] p = s.toCharArray();
           
           next[0] = -1;//所有的下标为0的next[]的值都为-1
           if(len == 1)return next;//如果只有一个元素则退出这个函数
           next[1] = 0;//所有下标为1的next[]的值都为0;
           
           int j = 1;//遍历原模式串的指针
           int k = next[j];//
           
           while(j<len-1) {
               if(k<0 || p[j]==p[k]) {
                   next[++j] = ++k;//当怕[j]字符等于p[k]字符,next数组指针向前移动一个单位,k加一
               }else {
                   k = next[k];
               }
           }
           return next;
       }

**与给定串进行匹配的方法**

/**
        * 计算模式串与原串匹配成功的次数
        * @param org 原串
        * @param pat 模式串
        * @return int
        */
       static int countPattren(String org,String pat) {
           if(org.length() == 0 || pat.length()==0)  return -1;
           if(pat.length()>org.length()) return -1;
           
           int org_len = org.length();
           int pat_len = pat.length();
           int i=0,j=0;
           int[] next = test_kmp.next(pat);
           int cnt = 0;
           while(i<org_len) {
               if(j == -1 || org.charAt(i) ==  pat.charAt(j)) {
                   i++;
                   j++;
               }else {
                   j = next[j];
               }
               if(j == pat_len) {
                   cnt++;
                   i--;
                   j = next[j-1];
               }
           }
           return cnt;
       }