玩转KMP算法

KMP算法

• Introduce
  • kniff-morris-praft

代码实现

• Java 代码实现

package xyz.standalon.advance;

import java.util.ArrayList;
import java.util.List;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-14 20:13
 * @desc:   Knuth-Morris-Pratt
 *  m:  length of pattern
 *  n:  length of text
 *  time: O(m + n)
 *  space
 */
public class KMPAlgorithm {
    public static int[] calcPrefixLen(String pattern) {
        int patternLen = pattern.length();
        int[] arr = new int[patternLen + 1];
        arr[0] = -1;
        arr[1] = 0;
        int prefixLen = 0;
        int i = 1;
        while (i < patternLen) {
            if (pattern.charAt(prefixLen) == pattern.charAt(i)) {
                prefixLen++;
                i++;
                arr[i] = prefixLen;
            } else if (prefixLen > 0) {
                prefixLen = arr[prefixLen]; // 此时不会让变量 i 自增
            } else {
                i++;
                arr[i] = 0; // 'prefixLen' reached 0,so save that into arr[] and move forward
            }
        }
        return arr;
    }

    public static List<Integer> search(String text, String pattern) {
        int t = 0; // the position of current character in text;
        int p = 0; // the position of current character in pattern;
        int tLen = text.length();
        int pLen = pattern.length();

        List<Integer> matches = new ArrayList<>();
        int[] prefixLen = calcPrefixLen(pattern);

        while (t < tLen) {
            if (pattern.charAt(p) == text.charAt(t)) {
                p++;
                t++;

                if (p == pLen) {
                    // 匹配成功,occurrence found, if only first occurrece is needed then you could halt there
                    matches.add(t - p);
                    p = prefixLen[p];   //reset
                }
            } else {
                p = prefixLen[p];
                if (p < 0) {
                    t++;
                    p++;
                }
            }
        }
        return matches;
    }
}

• Python 代码实现

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-14 17:57
 * @desc: KMP 算法
 */
    def Build(p: str) -> List[int]:
        m = len(p)
        nex = [0,0]
        j = 0
        for i in range(1,m):
            while j > 0 and p[i] != p[j]:
                j = nxt[j]
            if p[i] == p[j]:
                j +=1
            nxt.append(j)
        return nxt

    def Match(s: str,p: str) -> List[int]:
        n,m = len(s), len(p)
        nxt = Build(p)
        ans = []
        j = 0
        for i in range(n):
            while j > 0 and s[i] != p[j]:
                j = nxt[j]
            if s[i] = p[j]
                j += 1
            if j == m:
                ans.append(i - m + 1)
                j = nxt[j]
        return ans