字符串匹配算法

一、单模式串匹配

1.BF和RK算法

(1)BF（暴力匹配算法）

    public int BF(char[] target, char[] pattern) {
        if (target == null || pattern == null || target.length < pattern.length) return -1;
        int tLen = target.length;
        int pLen = pattern.length;
        for (int i = 0; i < tLen - pLen + 1; i++) {
            int j = 0;
            for (; j < pLen; j++) {
                if (target[i + j] != pattern[j]) {
                    break;
                }
            }
            if (j == pLen) {
                return i;
            }
        }
        return -1;
    }

(2)RK算法

选择的hash算法是26进制转换一个数，不会存在冲突，可能会存在溢出，代码并未处理。
代码中省略部分为优化前

    public int RK(char[] target, char[] pattern) {
        if (target == null || pattern == null || target.length < pattern.length) return -1;
        int tLen = target.length;
        int pLen = pattern.length;
        int[] hashCache = new int[pLen];
        int sum = 1;
        for (int i = 0; i < hashCache.length; i++) {
            hashCache[i] = sum;
            sum *= 26;
        }
        //模式串hash
        int pHash = 0;
        for (int i = 0; i < pLen; i++) {
            pHash += (pattern[i] - 'a') * hashCache[pLen - i - 1];
        }
        //主串中子串hash
        int[] targetChildHash = new int[tLen - pLen + 1];
        for (int i = 0; i < pLen; i++) {
            targetChildHash[0] += (target[i] - 'a') * hashCache[pLen - i - 1];
        }
        for (int i = 1; i < targetChildHash.length; i++) {
//            int hash = 0;
//            for (int j = 0; j < pLen; j++) {
//                hash += (target[i + j] - 'a') * hashCache[pLen - j - 1];
//            }
//            targetChildHash[i] = hash;
            targetChildHash[i] = (targetChildHash[i - 1] - hashCache[pLen - 1] * (target[i - 1] - 'a')) * 26 + (target[i + pLen - 1] - 'a') * hashCache[0];
        }
        //比较
        for (int i = 0; i < targetChildHash.length; i++) {
            //该hash算法不会存在冲突。如果会出现hash冲突，还需要继续判断对比子串和模式串是否相等
            if (targetChildHash[i] == pHash) {
                return i;
            }
        }
        return -1;
    }

关于优化部分讲解：
假设模式串长度m=3。主串中相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式是有交集的：

优化公式推导：

2.BM算法

public class BM {

    private static final int SIZE = 256;

    public static int bm(char[] target, char[] pattern) {
        if (target == null || pattern == null || target.length < pattern.length) return -1;
        int[] bc = new int[SIZE];
        generateBC(bc, pattern);
        int tLen = target.length;
        int pLen = pattern.length;
        int[] suffix = new int[pLen];
        boolean[] prefix = new boolean[pLen];
        generateGS(suffix, prefix, pattern, pLen);

        int i = 0;
        while (i <= tLen - pLen) {
            //1.坏字符规则
            int j = pLen - 1;
            for (; j >= 0; j--) {
                if (target[i + j] != pattern[j]) {//此时j是坏字符对应的模式串下标
                    break;
                }
            }
            if (j < 0) {//匹配成功
                return i;
            }
            int x = j - bc[(int) target[i + j]];
            int y = 0;
            //2.好后缀规则
            if (j < pLen - 1) {// 如果有好后缀（j+1~pLen-1为好后缀）
                y = getGS(j, suffix, prefix, pLen);
            }
            i = i + Math.max(x, y);//如果是i + (j - bc[(int) target[i + j]]),相当于模式串往后滑动j - bc[(int) target[i + j]]位
        }

        return -1;
    }

    private static int getGS(int j, int[] suffix, boolean[] prefix, int pLen) {
        int k = pLen - j - 1;//好后缀长度
        if (suffix[k] != -1) return j - suffix[k] + 1;//1.模式串存在好后缀
        for (int r = pLen - j - 2; r >= 1; r--) {
            if (prefix[r]) {//2.模式串是否存在前缀与好后缀子串匹配
                return r;
            }
        }
        return pLen;//3.不存在匹配，直接滑动pLen
    }

    private static void generateGS(int[] suffix, boolean[] prefix, char[] pattern, int pLen) {
        for (int i = 0; i < pLen; i++) {
            suffix[i] = -1;
        }
        for (int i = 0; i < pLen - 1; i++) {
            int j = i;
            int k = 0;
            while (j >= 0 && pattern[j] == pattern[pLen - k - 1]) {
                ++k;
                suffix[k] = j;
                --j;
            }
            if (j == -1) {
                prefix[k] = true;
            }
        }
    }

    /**
     * 构建坏字符哈希表
     * <p>
     * 假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组来记录每个字符在模式串中出现的位置。
     * 数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。
     *
     * @param bc
     * @param pattern
     */
    public static void generateBC(int[] bc, char[] pattern) {
        for (int i = 0; i < bc.length; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < pattern.length; i++) {//从前往后遍历，记录最后面出现的位置
            int index = (int) pattern[i];
            bc[index] = i;
        }
    }

    public static void main(String[] args) {
        String t = "abababc";
        String p = "bc";
        System.out.println(bm(t.toCharArray(), p.toCharArray()));
    }
}

3.KMP算法

public class KMP {

    public static int kmp(char[] target, char[] pattern) {
        int pLen = pattern.length;
        int tLen = target.length;
        int[] next = getNexts(pattern, pLen);
        int j = 0;
        for (int i = 0; i < tLen; i++) {
            while (j > 0 && target[i] != pattern[j]) {
                j = next[j - 1] + 1;//遇到坏字符时，查询next数组，改变模式串匹配起点
            }
            if (target[i] == pattern[j]) {//相等继续往后匹配
                ++j;
            }
            if (j == pLen) {//匹配成功，返回下标
                return i - pLen + 1;
            }
        }
        return -1;
    }

    private static int[] getNexts(char[] pattern, int pLen) {
        int[] next = new int[pLen];
        next[0] = -1;// 0位置没得回溯
        int k = -1;// 当前最长可匹配前缀子串的结尾字符下标
        for (int i = 1; i < pLen; i++) {// i表示已匹配前缀的位置（当前待填充的数组下标）
            while (k != -1 && pattern[k + 1] != pattern[i]) {
                k = next[k];//没办法找到更长的可匹配前后缀了，回溯找次长可匹配前后缀
            }
            if (pattern[k + 1] == pattern[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }
}

二、多模式串匹配

1.Trie树

/**
 * 假设字符集只是'a'~'z'的情况
 */
public class Trie {

    private TreeNode root = new TreeNode('/');//根节点不存储数据

    public void insert(char[] text) {
        TreeNode p = root;

        for (int i = 0; i < text.length; i++) {
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                p.children[index] = new TreeNode(text[i]);
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }

    public boolean find(char[] text) {
        TreeNode p = root;
        for (int i = 0; i < text.length; i++) {
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (!p.isEndingChar) {// 不能完全匹配，只是匹配了前缀
            return false;
        }
        return true;
    }

    class TreeNode {

        public char data;
        public TreeNode[] children = new TreeNode[26];
        public boolean isEndingChar = false;

        public TreeNode(char data) {
            this.data = data;
        }
    }
}

2.AC自动机

public class AC {

    private AcNode root = new AcNode('/');

   /**
    * 将多个模式串构建成 AC 自动机
    */
    public AC(String[] pattern) {
        //1.通过多个模式串构建Trie树
        for (String p : pattern) {
            insert(p.toCharArray());
        }
        //2.在 Trie 树上构建失败指针
        buildFailurePointer();
    }

    /**
     * 构建失败指针
     */
    private void buildFailurePointer() {
        Queue<AcNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            AcNode p = queue.poll();
            for (int i = 0; i < 26; i++) {
                AcNode pc = p.children[i];
                if (pc == null) continue;
                if (p == root) {
                    pc.fail = root;
                } else {
                    AcNode q = p.fail;
                    while (q != null) {
                        AcNode qc = q.children[i];
                        if (qc != null) {
                            pc.fail = qc;
                            break;
                        }
                        q = q.fail;
                    }
                    if (q == null) {
                        pc.fail = root;
                    }
                }
                queue.add(pc);
            }
        }
    }

    public void insert(char[] data) {
        AcNode p = root;
        for (char c : data) {
            int index = c - 'a';
            if (p.children[index] == null) {
                p.children[index] = new AcNode(c);
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
        p.length = data.length;
    }

    /**
     * 多模式串匹配
     *
     * @param target
     */
    private void match(char[] target) {//target是主串
        AcNode p = root;
        for (int i = 0; i < target.length; i++) {
            int index = target[i] - 'a';
            if (p.children[index] == null && p != root) {
                p = p.fail;
            }
            p = p.children[index];
            if (p == null) {// 如果没有匹配的，从root开始重新匹配
                p = root;
            }
            AcNode tmpNode = p;
            while (tmpNode != root) {// 打印出可以匹配的模式串
                if (tmpNode.isEndingChar) {
                    int pos = i - tmpNode.length + 1;
                    System.out.println("匹配起始下标" + pos + "; 长度" + tmpNode.length);
                }
                tmpNode = tmpNode.fail;
            }
        }
    }

    class AcNode {
        public char data;
        public AcNode[] children = new AcNode[26];//字符集只包含a~z这26个字符
        public boolean isEndingChar = false;
        public AcNode fail = null;
        public int length = -1;//isEndingChar为true时候记录模式串长度

        public AcNode(char data) {
            this.data = data;
        }
    }


    public static void main(String[] args) {
        String[] pattern = {"abce", "bcd", "ce"};
        AC ac = new AC(pattern);
        String target = "cdbcdklce";
        ac.match(target.toCharArray());
    }
   
}