Live each day like it could be your last.
把每天都当作生命的最后一天, 认真生活.
大道至简, 我的理想是用最简单的代码实现最美的算法. 字符串匹配的应用非常广泛, java 的 indexOf(),JS 的全家桶一套匹配 (find,indexOf,include...) 等等. 本文主要分享了它们底层依赖的字符串匹配算法. 两种简单, 两种复杂. 话不多说, 所有源码均已上传至 GitHub: 链接 https://github.com/chaoaiqi/study
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
您的点赞和关注是对我最大的支持, 谢谢!
来源: https://juejin.im/post/5c87512f6fb9a049f571fcb5