漳州市网站建设,室内设计专用软件,政务网站源码,网站软件定制开发制作1、【Boyer-Moore 算法】
【算法】哪种算法有分数复杂度#xff1f;- BoyerMoore字符串匹配_哔哩哔哩_bilibili BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较#xff0c;而…1、【Boyer-Moore 算法】
【算法】哪种算法有分数复杂度- BoyerMoore字符串匹配_哔哩哔哩_bilibili BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较而会跳过其中某些部分。通常搜索关键字越长算法速度越快。它的效率来自于这样的事实对于每一次失败的匹配尝试算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征加快了搜索的步骤。 BM算法实际上包含两个并行的算法也就是两个启发策略坏字符算法bad-character shift和好后缀算法good-suffix shift。这两种算法的目的就是让模式串每次向右移动尽可能大的距离即上面的BM( )尽可能大。 一般情况下比KMP算法快3-5倍 package com.vedeng;public class BoyerMoore {private static final int NO_OF_CHARS 256;// 预处理坏字符规则private static void badCharHeuristic(char[] str, int size, int[] badChar) {for (int i 0; i NO_OF_CHARS; i) {badChar[i] -1;}for (int i 0; i size; i) {badChar[(int) str[i]] i;}}// Boyer-Moore算法实现public static void search(char[] txt, char[] pat) {int m pat.length;int n txt.length;int[] badChar new int[NO_OF_CHARS];// 预处理坏字符规则badCharHeuristic(pat, m, badChar);int s 0; // s是shift的缩写表示模式串相对于文本串的偏移while (s (n - m)) {int j m - 1;// 从右向左匹配while (j 0 pat[j] txt[s j]) {j--;}// 如果匹配成功打印匹配的位置if (j 0) {System.out.println(Patterns occur at shift s);// 根据好后缀规则计算下一个可能的偏移s (s m n) ? m - badChar[txt[s m]] : 1;} else {// 根据坏字符规则计算下一个可能的偏移s Math.max(1, j - badChar[txt[s j]]);}}}public static void main(String[] args) {char[] txt ABAAABCD.toCharArray();char[] pat ABC.toCharArray();search(txt, pat);}
} 相关
https://blog.csdn.net/qq_43197840/article/details/140680860?spm1001.2014.3001.5501 https://blog.csdn.net/qq_43197840/article/details/140680621?spm1001.2014.3001.5501
