KMP算法

KMP算法

暴力解决

  • 思路

    从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,重新开始匹配。

    我们可以这样初始化:

  • 代码

    public class KMP {
        public static int kmp(String a,String b){
            char[] arr = a.toCharArray();
            char[] brr = b.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                int tmp = i;
                for (int j = 0; j < brr.length; j++,tmp++) {
                    if(arr[tmp] != brr[j]){
                        break;
                    }
                }
                if((tmp - i) == brr.length){
                    return tmp - i - 1;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            String ts = "abcabde";
            String ps = "abde";
            System.out.println(kmp(ts,ps));
        }
    }
    

优化(动态规划)

  • 思路

    备忘录,记录匹配串的最长前缀下标,匹配失败回退时可以退到最佳位置,减少回溯的次数

  • 代码

    public class KMP {
    
        public static int KMP(String ts,String ps){
            char[] t = ts.toCharArray();
            char[] p = ps.toCharArray();
            int i = 0;//主串
            int j = 0;//模式串
            int[] next = getNext(ps);
            while (i < t.length && j < p.length){
               if(j == -1 || t[i] == p[j]){
                   i++;
                   j++;
               }else {
                   j = next[j];
               }
            }
            return j == p.length ? i - j : -1;
        }
    
        public static int[] getNext(String ps){
            char[] p = ps.toCharArray();
            int[] next = new int[p.length];
            next[0] = -1;
            int i = 0;
            int k = -1;
            while (i < next.length - 1){
                if(k == -1 || p[i] == p[k]){
                    next[++i] = ++k;
                }else {
                    k = next[k];
                }
            }
            return next;
        }
    
        public static void main(String[] args) {
            String ts = "ssssssssssb";
            String ps = "abcabcmn";
            System.out.println(KMP(ts,ps));
        }
    }
    
  • 参考文章:https://www.cnblogs.com/yjiyjige/p/3263858.html

上一篇:MySQL备份


下一篇:sqlyog导入sql文件