Live each day like it could be your last.
把每天都当作生命的最后一天，认真生活。
引言
大道至简，我的理想是用最简单的代码实现最美的算法。字符串匹配的应用非常广泛，java的indexOf(),js的全家桶一套匹配(find，indexOf,include...)等等。本文主要分享了它们底层依赖的字符串匹配算法。两种简单，两种复杂。话不多说，所有源码均已上传至github:链接
BF算法
bf算法俗称朴素匹配算法，为什么叫这个名字呢，因为很暴力，在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
解析
在这里i循环是跟踪主串txt,j是跟踪模式串pattern，首先外围先确定访问次数，tLen-pLen。
j循环来进行比较，这里可能唯一比较不好理解的是i + j，查看测试结果，应该可以明白。
private int bfSearch(String txt, String pattern) {
int tLen = txt.length();
int pLen = pattern.length();
if (tLen < pLen) return -1;
for (int i = 0; i <= tLen - pLen; i++) {
int j = 0;
for (; j < pLen; j++) {
System.out.println(txt.charAt(i + j) + " -- " + pattern.charAt(j));
if (txt.charAt(i + j) != pattern.charAt(j)) break;
}
if (j == pLen) return i;
}
return -1;
}复制代码变体
bf算法还有一个变化，用到了显示回退的思想，i，j的作用和常规的一样，这里的i相当于常规的i+j,只不过当发现不匹配的时候，需要回退i和j这两个指针，j重新回到开头，i指向下一个字符。
private int bfSearchT(String txt, String pattern) {
int tLen = txt.length();
int i = 0;
int pLen = pattern.length();
int j = 0;
for (; i < tLen && j < pLen; i++) {
System.out.println(txt.charAt(i) + " -- " + pattern.charAt(j));
if (txt.charAt(i) == pattern.charAt(j)) {
++j;
} else {
i -= j;
j = 0;
}
}
if (j == pLen) {
System.out.println("end... i = " + i + ",plen = " + pLen);
return i - pLen;
}
return -1;
}复制代码测试代码
ps： hello world
public static void main(String[] args) {
BFArithmetic bf = new BFArithmetic();
String txt = "hello world";
String pattern = "world";
int res = bf.bfSearch(txt, pattern);
System.out.println("BF算法匹配结果:" + res);
// int resT = bf.bfSearchT(txt, pattern);
// System.out.println("BF算法(显示回退)匹配结果:" + resT);
}复制代码测试结果
RK算法
rk算法相当于bf算法的进阶版，它主要是引入了哈希算法。降低了时间复杂度。通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
初始化
这里要把模式串预制进去，生成相对应的hash值，然后随机生成一个大素数，便于后续的使用。
private RKArithmetic(String pattern) {
this.pattern = pattern;
pLen = pattern.length();
aLen = 256;
slat = longRandomPrime();
System.out.println("随机素数：" + slat);
aps = 1;
// aLen^(pLen - 1) % slat
for (int i = 1; i <= pLen - 1; i++) {
aps = (aLen * aps) % slat;
}
patHash = hash(pattern, pLen);
System.out.println("patHash = " + patHash);
}复制代码准备
随机生成一个大素数
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}复制代码哈希算法
private long hash(String txt, int i) {
long h = 0;
for (int j = 0; j < i; j++) {
h = (aLen * h + txt.charAt(j)) % slat;
}
return h;
}复制代码校验字符串是否匹配
private boolean check(String txt, int i) {
for (int j = 0; j < pLen; j++)
if (pattern.charAt(j) != txt.charAt(i + j))
return false;
return true;
}复制代码实现
该实现还是比较容易阅读的，只不过将比较换成了hash值的比较。
private int rkSearch(String txt) {
int n = txt.length();
if (n < pLen) return -1;
long txtHash = hash(txt, pLen);
if ((patHash == txtHash) && check(txt, 0))
return 0;
for (int i = pLen; i < n; i++) {
txtHash = (txtHash + slat - aps * txt.charAt(i - pLen) % slat) % slat;
txtHash = (txtHash * aLen + txt.charAt(i)) % slat;
int offset = i - pLen + 1;
System.out.println("第" + offset + "次txtHash = " + txtHash);
if ((patHash == txtHash) && check(txt, offset))
return offset;
}
return -1;
}复制代码测试代码
public static void main(String[] args) {
String pat = "world";
String txt = "hello world";
RKArithmetic searcher = new RKArithmetic(pat);
int res = searcher.rkSearch(txt);
System.out.println("RK算法匹配结果：" + res);
}复制代码测试结果
KMP算法
未完待续...
BM算法
未完待续...
end
您的点赞和关注是对我最大的支持，谢谢！
