欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串部分:子字符串查找

程序员文章站 2022-03-05 10:41:41
...

子字符串查找

在母串中匹配对应的模式串(pattern)

暴力查找

public class PatternMatch {
    public static int search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            // j 主要是用来遍历模式串
            for (j = 0; j < M; j++) {
                if (txt.charAt(i + j) != pat.charAt(j)) break;
            }
            if (j == M) return i;
        }
        return N;
    }

    public static int search2(String pat, String txt) {
        int j, M = pat.length();
        int i, N = txt.length();

        for (i = 0, j = 0; i < N && j < M; i++) {
            if (txt.charAt(i) == pat.charAt(j)) j++;
            else {
                i -= j; // 如果在这个位置匹配失败,那么i可以直接移步到这个位置,而不是往后进一位
                j = 0;
            }
        }
        return j == M ?
                i - M : // 找到匹配
                N; // 未找到匹配
    }
}

KMP算法

推荐B站UP主,正月点灯笼的讲解视频

基本思想:出现不匹配时,就能知晓一部分文本的内容;避免将指针回退到所有这些已知晓的字符之前

字符串部分:子字符串查找

  • 首先需要获取模式串的所有前缀表

字符串部分:子字符串查找

  • 构造前缀表,通过最长公共前后缀来计算

字符串部分:子字符串查找

  • 第一次匹配失败,根据前缀表,退到数组序号为1的位置

字符串部分:子字符串查找

  • 第二次匹配失败退到数组为0的位置

字符串部分:子字符串查找

  • 0号匹配失败,数组移动到-1,表示整个字符串往右移动一位

构造最长公共前后缀数组:

字符串部分:子字符串查找

  • 前缀为2,那么必须是前一个串再后面加了一个字符,这个字符的值和前一个串的第二位是相等的(动态规划)

整体算法:

public class KMP {

    private static List<Integer> matches = new ArrayList<>();

    public static int[] prefixTable(String pattern) {

        char[] array = pattern.toCharArray();
        int n = array.length;
        int[] prefix = new int[n];
        prefix[0] = 0;

        // len 表示公共前后缀长度
        int len = 0, i = 1;
        while (i < n) {
            if (array[i] == array[len]) {
                len++;
                prefix[i] = len;
                i++;
            } else {
                if (len > 0) {
                    // 斜着对应
                    // len的值替换为前一位的后缀长度
                    len = prefix[len - 1];
                } else {
                    // i一开始会出现死循环,第一位要置为0,然后i++退出死循环
                    prefix[i] = len;
                    // i++退出循环
                    i++;
                }
            }
        }
        return prefix;
    }

    public static void movePrefixTable(int[] prefix) {
        for (int i = prefix.length - 1; i > 0; i--) {
            prefix[i] = prefix[i - 1];
        }
        prefix[0] = -1;
    }

    public static void kmpSearch(String text, String pattern) {
        // 定义前缀表
        int[] prefix = prefixTable(pattern);
        movePrefixTable(prefix);

        char[] t = text.toCharArray();
        char[] p = pattern.toCharArray();

        int m = t.length, n = p.length;
        // i是母串的游标,j是模式串的游标
        int i = 0, j = 0;

        while (i < m) {
            // 当模式串到达末尾且此时与对应母串的字符相等,代表找到了子串
            if (j == n - 1 && t[i] == p[j]) {
                System.out.println("Found pattern at " + (i - j));
                // 将所有匹配的串的开始位置加入到列表中
                matches.add(i - j);
                // 找到一个不代表找完,还会继续查找
                j = prefix[j];
            }
            // 相等,那么两个游标都向右移动
            if (t[i] == p[j]) {
                i++;
                j++;
            } else {
                // 如果不相等,模式串的游标进行回退操作,根据前缀表进行回退
                // 这个时候母串的游标不移动
                j = prefix[j];
                // 当模式串退到首位时,i、j两者都要+1,这样会j到了0位
                // 模式串整体向右移动一位
                if (j == -1) {
                    i++;
                    j++;
                }
            }
        }

    }

    public static void main(String[] args) {
        String pattern = "ABA";
        String text = "ABAABAABAABC";
        kmpSearch(text, pattern);
        matches.forEach(i -> System.out.print(i + " "));
    }

}

Rabin-Karp指纹识别算法

核心思想:高效计算文本中i+1位置的字符串散列值。通过多位的字符串取模,对比大小进行判定。核心就是计算散列值然后取模比较,总体还是比较简单,KMP比较难

public class RabinKarp {
    private String pat;
    private long patHash;
    private int M;
    private long Q;
    private int R;
    private long RM;

    public RabinKarp(String pat) {
        this.pat = pat;

        this.M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M - 1; i++) {
            RM = (R * RM) % Q; // 减去第一个数字时的计算
        }
        patHash = hash(pat, M);
    }

    private long hash(String key, int m) {
        long h = 0;
        for (int j = 0; j < m; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    private boolean check(int i) {
        return true;
    }

    // a random 31-bit prime
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    private int search(String txt) {
        int N = txt.length();
        long txtHash = hash(txt, M);
        // 一开始就匹配成功
        if (patHash == txtHash && check(0)) return 0;
        for (int i = 1; i < N; i++) {
            // 计算散列值
            //散列值的移位方式,先减去首位,再乘上RM,加上最后一个数字,再执行匹配
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            if (patHash == txtHash) {
                if (check(i - M + 1))
                    return i - M + 1;
            }
        }
        return N; //未找到匹配
    }
}
相关标签: LeetCode 字符串