← 返回学习路线

SYSTEM

匹配

Java基础匹配system
src/content/notes/system/匹配.md

匹配

BF

Brute Force 暴力匹配算法:

public static void main(String[] args) {
    String s = "seazean";
    String t = "az";
    System.out.println(match(s,t));//2
}

public static int match(String s,String t) {
    int k = 0;
    int i = k, j = 0;
    //防止越界
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) {
            ++i;
            ++j;
        } else {
            k++;
            i = k;
            j = 0;
        }
    }
    //说明是匹配成功
    if (j >= t.length()) {
        return k;
    }
    return 0;
}

平均时间复杂度:O(m+n),最坏时间复杂度:O(m*n)


RK

把主串得长度记为 n,模式串得长度记为 m,通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小,如果某个子串的哈希值与模式串相等,再去对比值是否相等(防止哈希冲突),那就说明对应的子串和模式串匹配了

因为哈希值是一个数字,数字之间比较是否相等是非常快速的

第一部分计算哈希值的时间复杂度为 O(n),第二部分对比的时间复杂度为 O(1),整体平均时间复杂度为 O(n),最坏为 O(n*m)


KMP

KMP 匹配:

  • next 数组的核心就是自己匹配自己,主串代表后缀,模式串代表前缀
  • nextVal 数组的核心就是回退失配
public class Kmp {
    public static void main(String[] args) {
        String s = "acababaabc";
        String t = "abaabc";
        //[-1, 0, 0, 1, 1, 2]
        System.out.println(Arrays.toString(getNext(t)));
        //[-1, 0, -1, 1, 0, 2]
        System.out.println(Arrays.toString(getNextVal(t)));
        //5
        System.out.println(kmp(s, t));
    }

    private static int kmp(String s, String t) {
        int[] next = getNext(t);
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            //j==-1时说明第一个位置匹配失败,所以将s的下一个和t的首字符比较
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                //模式串右移,比较s的当前位置与t的next[j]位置
                j = next[j];
            }
        }
        if (j >= t.length()) {
            return i - j + 1;
        }
        return -1;
    }
	//next数组
    private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        next[0] = -1;
        int j = -1;
        int i = 0;
        while (i < t.length() - 1) {
            // 根据已知的前j位推测第j+1位
            // j=-1说明首位就没有匹配,即t[0]!=t[i],说明next[i+1]没有最大前缀,为0
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                // 因为模式串已经匹配到了索引j处,说明之前的位都是相等的
                // 因为是自己匹配自己,所以模式串就是前缀,主串就是后缀,j就是最长公共前缀
                // 当i+1位置不匹配时(i位之前匹配),可以跳转到j+1位置对比,next[i+1]=j+1
                i++;
                j++;
                next[i] = j;
            } else {
                //i位置的数据和j位置的不相等,所以回退对比i和next[j]位置的数据
                j = next[j];
            }

        }
        return next;
    }
	//nextVal
    private static int[] getNextVal(String t) {
        int[] nextVal = new int[t.length()];
        nextVal[0] = -1;
        int j = -1;
        int i = 0;
        while (i < t.length() - 1) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                // 如果t[i+1] == t[next(i+1)]=next[j+1],回退后仍然失配,所以要继续回退
                if (t.charAt(i) == t.charAt(j)) {
                    nextVal[i] = nextVal[j];
                } else {
                    nextVal[i] = j;
                }
            } else {
                j = nextVal[j];
            }
        }
        return nextVal;
    }
}

平均和最坏时间复杂度都是 O(m+n)

参考文章:https://www.cnblogs.com/tangzhengyue/p/4315393.html


树

二叉树

二叉树中,任意一个节点的度要小于等于 2

  • 节点:在树结构中,每一个元素称之为节点
  • 度:每一个节点的子节点数量称之为度
二叉树结构图