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
- 节点:在树结构中,每一个元素称之为节点
- 度:每一个节点的子节点数量称之为度