数据结构与算法-字符串的匹配

BF算法（buter force）

原理：分为主串和模串，在主串m中匹配模串n，所以主串有从0,1,2,3….到m-n个m-n+1个子字符串

时间复杂度：理论上是O(m*n),m是主串长度，n是子串长度。但是因为匹配到模串第一个不符合的就会返回进行下一次匹配所以实际效果会好不上。加上比较简单、易于排错所以一般工业会采用这种方法

代码示例：

public class BruteForce {
    private char[] main;
    private char[] pattern;


    public BruteForce(String main, String pattern) {
        this.main = main.toCharArray();
        this.pattern = pattern.toCharArray();
    }

    //暴力搜索的方法，总共有起始位置0，1，2，...n,m-n+1个子串，每个子串和摩串匹配时间复杂度是O(m-n)
    public int indexOf() {
        if (main.length < pattern.length) {
            return -1;
        }
        boolean eq = true;
        for (int i = 0; i <= main.length - pattern.length + 1; i++) {
            for (int j = 0; j < pattern.length; j++) {
                if (main[i + j] != pattern[j]) {
                    eq = false;
                    break;
                }
                eq = true;
            }

            if (eq) {
                return i;
            }
        }
        return -1;
    }
}

RK算法-RobinKrap

BF算法的优化，由于BF算法需要一个个比较子串，复杂度是O(m*n),所以KR对BF算法做了优化，预先将所有的子串的hash值计算出来然后吧子串的位置记录下来，计算模串的hash，然后在hash中查找，这样复杂度就是计算模串的O(n)+hash获取的O(1)。

代码

 public class RobinKrap {
    private char[] main;
    private char[] pattern;

    private Integer patternHash;

    private Map<Integer, Integer> hashMap = new HashMap<>();

    //本质和bf的方法一样，只是预先将0~m-n个n-m+1个子串的hash和位置预先计算出来保存起来，然后在查询时候用模的hash去匹配看是否存在
    public RobinKrap(String main, String pattern) {
        this.main = main.toCharArray();
        this.pattern = pattern.toCharArray();

        patternHash = this.pattern.hashCode();

        for (int i = 0; i < main.length() - pattern.length() + 1; i++) {
            hashMap.put(Arrays.copyOfRange(this.main, i, pattern.length()).hashCode(), i);
        }
    }


    public int indexOf() {
        return hashMap.containsKey(patternHash)?hashMap.get(patternHash):-1;
    }

    public static void main(String[] args) {
        String s = "abcdefghijklmnklmn";
        String p = "klmn";
        BruteForce bf = new BruteForce(s, p);
        int i = bf.indexOf();
        System.out.println(i);
        for (int idx = i; idx < i + p.length(); idx++) {
            System.out.print(s.charAt(idx));
        }
        System.out.println();
    }

}