串的模式匹配算法KMP（java）

串的模式匹配算法KMP（java） 一、串的模式匹配算法

  子串的定位 *** 作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置。下面时一种不依赖于其他串 *** 作的暴力匹配算法，最坏时间复杂度为 O ( m ∗ n ) O(m*n) O(m∗n)。

public static int violenceMatch(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] s2 = p.toCharArray();
        int i = 0, j = 0;
        while (i < s1.length && j < s2.length) {
            if (s1[i] == s2[j]) {
                i++;
                j++;
            } else {
                i = i - (j - 1);
                j = 0;
            }
        }
        if (j == s2.length) {
            return i - j;
        } else {
            return -1;
        }
    }

二、KMP算法

  在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

1、字符串的前缀，后缀和部分匹配值

  前缀：除最后一个字符以外，字符串的所有头部子串；
  后缀：除第一个字符以外，字符串的所有尾部部子串；
  部分匹配值：字符串的前缀和后缀的最长相等的前后缀长度。

  例如：字符串“ABCABCD”：

“A”：前缀和后缀都是空集，最长相等前后缀长度为0；“AB” ：前缀为{A}，后缀为{B} ，{A}∩{B} = ∅，最长相等前后缀长度为0；“ABC”：前缀为{A，AB}，后缀为{，BC} ，{A，AB}∩{C，BC} = ∅，最长相等前后缀长度为0；“ABCA”：前缀为{A，AB，ABC}，后缀为{A，CA，BCA} ，{A，AB，ABC}∩{A，CA，BCA} = {A}，最长相等前后缀长度为1；“ABCAB”：前缀为{A，AB，ABC，ABCA}，后缀为{B，AB，CAB，BCAB} ，{A，AB，ABC，ABCA}∩{B，AB，CAB，BCAB} = {AB}，最长相等前后缀长度为2；“ABCABC”：前缀为{A，AB，ABC，ABCA，ABCAB}，后缀为{C，BC，ABC，CABC，BCABC} ，{A，AB，ABC，ABCA，ABCAB}∩{C，BC，ABC，CABC，BCABC} = {ABC}，最长相等前后缀长度为3；“ABCABCD”：前缀为{A，AB，ABC，ABCA，ABCAB}，后缀为{D，CD，BCD，ABCD，CABCD，BCABCD} ，{A，AB，ABC，ABCA，ABCAB，ABCABC}∩{D，CD，BCD，ABCD，CABCD，BCABCD} = ∅，最长相等前后缀长度为0。

字符串“ABCABCD”的部分匹配值（Partial Match，PM）为0001230：

编号1234567SABCABCDPM0001230 2、利用PM表进行匹配：

  主串：ABCABCABCABCDAB
  子串：ABCABCD

第一趟匹配：

  发现B和D不匹配，前面6个字符是匹配的，查表可知，最后一个匹配字符C对应的部分匹配值为3，因此按照下面的公式算出子串需要向后移动的位数：

        移动位数 = 已匹配的字符串数 - 对应的部分匹配值

  因为6 - 3 = 3 ，所以子串向后移动3位，进行
第二趟匹配：

  发现A和D不匹配，查表可知，最后一个匹配字符C对应的部分匹配值为0，所以子串向右移动 6 - 3 = 3 位， 进行第三趟匹配：

  匹配完成，时间复杂度为 O ( m + n ) O(m+n) O(m+n)。

3、KMP原理

        移动位数 = 已匹配的字符串数 - 对应的部分匹配值

  公式的意义：如图所示，

  当A与D匹配时，已匹配“ABCABC”的前缀“ABC”和后缀“ABC”为最长公共元素。已知前缀“ABC”与“BCA”（黄色部分）、“CAB”（红字部分）均不同，与后缀“ABC”相同，故无须比较，直接将子串移动“已匹配的字符数-对应的部分匹配值”，用子串前缀后面的元素与主串匹配失败的元素开始比较即可，如图所示。

4、代码实现

package com.haiyang.algorithm.KMP;

import java.util.Arrays;


public class Kmp {
    public static void main(String[] args) {
        String s1 = "ABCABCABCABCDAB";
        String s2 = "ABCABCD";
        int[] pm = partialMatch(s2);
        int index = kmpMatch(s1, s2, pm);
        System.out.println(index);
    }

    
    public static int kmpMatch(String s1, String s2, int[] pm) {
        for (int i = 0, j = 0; i < s1.length(); i++) {
            //根据pm表，向右移动
            //KMP核心代码
            while (j > 0 && s1.charAt(i) != s2.charAt(j)) {
                j = pm[j - 1];
            }
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            if (j == s2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    
    public static int[] partialMatch(String str) {
        int[] pm = new int[str.length()];
        //长度为1时，初始化值为0
        pm[0] = 0;
        for (int i = 1, j = 0; i < str.length(); i++) {
            //KMP核心代码
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = pm[j - 1];
            }

            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }

            pm[i] = j;
        }
        return pm;
    }
}