动态规划(二,kmp算法)

sjy.png

概述:

kmp算法是一种改进的字符串匹配算法.
kmp算法的核心思想是利用比对失败的信息,减少模式串与目标串的比对次数.

步骤:

• 首先我们要用模式串生成一个next数组

  
  image.png
  

  生成的规则就是:当后面的字母与开头相同时,就填123,不同时就返回到0.

构建next数组的规则:

1. 首先把next[0] = 0;
2. 遍历目标串dest,比较dest[i]和dest[j]是否相等(i为dest的字母的下标,j为next数组的下标),如果不相等
   j = next[j-1];
3. 如果相等 j++;
4. next[i] = j;

• 然后模式串与目标串进行比对

  
  image.png
  

  当出现不相同时,将模式串回退,回退的位置为 以原位置j-1为next数组下标取值,如图中next[7-1]值为2,就回退到aba的位置,继续与目标串比对.

代码:

import org.junit.Test;

public class kmp {

    public int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        //开始推出next
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //3
            while (j > 0 && dest.charAt(j) != dest.charAt(i)) {
                j = next[j - 1];
            }
            //1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            //2
            next[i] = j;
        }
        return next;
    }

    /**
     * 目标串与模式串比较
     * 返回比对完成时,目标串的位置
     *
     * @param str
     * @param dest
     * @param next
     * @return
     */
    private int kmp(String str, String dest, int[] next) {
        for (int i = 0, j = 0; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            if (str.charAt(i) == dest.charAt(j)) {
                j++;
            }
            if (j == dest.length()) {//结束
                return i - j + 1;
            }
        }
        return 0;
    }

    @Test
    public void test() {
        String str = "ababcabcbababcabacaba";
        String dest = "ababcaba";
        int[] array = kmpNext(dest);
        System.out.println(kmp(str, dest, array));
    }

}