精华内容
下载资源
问答
  • 字符串匹配算法
    2020-03-20 15:51:40

    字符串匹配算法

    匹配原理:

    字符串A :a b c d e f h
    字符串B : c d e f

    通过观察可知,字符串B是字符串A的子串,且B在A中第一次出现的位置是2,所以直接返回2,若无法匹配到子串则返回-1,一般我们统一将这里的A称为主串,B称为模式串。

    方法一:BF算法(Brute Force 暴力算法)

    暴力匹配法,即从主串的首位开始,把主串和模式串的字符进行逐个比较,若第一位就不同,则将模式串进行后移一位,再次重新开始比较;若第一位相同,则进行主串与模式串的第二位,第三位的依次比较。

    1. 假设主串的长度是m,模式串的长度是n,BF算法的最坏时间复杂度为O(mn);
    2. 该种方法实现简单,但是执行效率很低

    方法二:RK算法(Rabin-Karp 哈希匹配算法)

    哈希匹配法,即将原先主串和模式串的字符比较转换成对应哈希值比较,这样的要容易得多。具体的哈希转换方法有很多,例如,按位相加法、转换成26进制法。由于主串通常要长于模式串,把整个主串转化成hashcode是没有意义的,只有比较主串当中和模式串等长的子串才有意义,当哈希值相等时,再模仿BF算法,进行两个字符串的逐项比较。
    hashcode = hash(string)

    1. 哈希法可以通过优化字符串累加方法,即新子串的hash值都用上一次子串进行简单的增量来计算;
    2. 通使用优化方法,最终RK算法的时间复杂度可以优化为O(n);
    3. 与BF算法相比,免去了很多无谓的字符比较,时间复杂度上有很大提高;
    4. RK算法的缺点在于哈希冲突,每一次哈希冲突时都要进行子串和模式串的逐个比较,如果冲突过多,RK算法就会退化成BF算法。

    RK算法代码如下.

    public static int rabinKarp (String str, String pattern){   
    	//主串长度   
    	int m = str.length();   
    	//模式串的长度   
    	int n = pattern.length();   
    	//计算模式串的hash值 
    	int patternCode = hash(pattern);  
    	//计算主串当中第一个和模式串等长的子串hash值  
    	int strCode = hash(str.substring(0,n));
    
    	//用模式串的hash值和主串的局部hash值比较。
    	//如果匹配,则进行精确比较;如果不匹配,计算主串中相邻子串的hash值。   
    	for (int i = 0; i<m-n+1; i++){
    	        if(strCode == patternCode && compareString(i, str, pattern)){           
    				return i;     
    				}
    			//如果不是最后一轮,更新主串从i到i+n的hash值
    	        if(i<m-n){
    	            strCode = nextHash(str, strCode, i, n);
    	        
    				}
    	    }
    	return -1;}
    
    private static int hash(String str){    
    	int hashcode = 0;    
    	//这里采用最简单的hashcode计算方式:    
    	//把a当做1,把b当中2,把c当中3.....然后按位相加    
    	for (int i = 0; i < str.length(); i++) {        
    		hashcode += str.charAt(i)-'a';    
    		}    
    	return hashcode;
    }
    
    private static int nextHash(String str, int hash, int index, int n){    
    	hash -= str.charAt(index)-'a';    
    	hash += str.charAt(index+n)-'a';    
    	return hash;
    }
    
    private static boolean compareString(int i, String str, String pattern) {
       String strSub = str.substring(i, i+pattern.length());    
       return strSub.equals(pattern);
    }
    
    public static void main(String[] args) {    
    	String str = "aacdesadsdfer";    
    	String pattern = "adsd";    
    	System.out.println("第一次出现的位置:" + rabinKarp(str, pattern));
    

    方法三:BM算法(坏字符和好后缀算法)

    坏字符规则

    即是指模式串和子串当中不匹配的字符,当模式串和主串的第一个等长子串比较时,从右侧开始确定坏字符(检测顺序相反,是从字符串最右侧向最左侧检测),如果坏字符在模式串中不存在,则直接把模式串挪到主串坏字符的下一位。

    1. 坏字符的位置越靠右,下一轮模式串的挪动跨度就可能越长,节省的比较次数也就越多;
    //在模式串中,查找index下标之前的字符是否和坏字符匹配
    private static int findCharacter(String pattern, char badCharacter, int index) {    
    	for(int i= index-1; i>=0; i--){        
    		if(pattern.charAt(i) == badCharacter){            
    			return i;        
    			}    
    		}  
    		//模式串不存在该字符,返回-1    
    	return -1;
    	}
    
    public static int boyerMoore(String str, String pattern) {    
    	int strLength = str.length();    
    	int patternLength = pattern.length();    
    	//模式串的起始位置    
    	int start = 0;    
    	while (start <= strLength - patternLength) {        
    		int i;        
    		//从后向前,逐个字符比较        
    		for (i = patternLength - 1; i >= 0; i--) {            
    			if (str.charAt(start+i) != pattern.charAt(i))
    			   //发现坏字符,跳出比较,i记录了坏字符的位置                
    				break;        
    				}        
    			if (i < 0) {
    			    //匹配成功,返回第一次匹配的下标位置            
    			    return start;        
    			    }        
    		//寻找坏字符在模式串中的对应        
    		int charIndex = findCharacter(pattern, str.charAt(start+i), i);        
    		//计算坏字符产生的位移        
    		int bcOffset = charIndex>=0 ? i-charIndex : i+1;        
    		start += bcOffset;    
    		}    
    		return -1;
    }
    
    public static void main(String[] args) {    
    	String str = "GTTATAGCTGGTAGCGGCGAA";    
    	String pattern = "GTAGCGGCG";    
    	int index = boyerMoore(str, pattern);    
    	System.out.println("首次出现位置:" + index);
    }
    

    好后缀规则

    好后缀就是指模式串和子串当中相匹配的后缀。即当子串和模式串不匹配时,但模式串和子串存在好后缀,且在模式串中可以找到与好后缀相同的片段,这样就可以直接移动模式串中的相同片段与模式串的好后缀对齐,从而实现快速位移;但是当不存在这样的相同片段时,切记不可一次性把模式串移动到好后缀的后面,要判断模式串的前缀是否与好后缀的后缀相匹配,以免移动过多而错过。

    何时采用坏字符或者好后缀规则,并没有直接结论,需要分别计算下一轮模式串移动的长度并进行比较,可以使模式串移动更多的规则,就是更好的方法。

    方法四:KMP算法(最长可匹配前后缀子串算法)

    即在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串,在下一轮直接把两者对齐,从而实现模式串的快速移动。而提前将这个前缀(next数组)找出来则是KMP算法的重点。
    详细算法原理讲解建议参看视频:【天勤公开课】KMP算法易懂版
    这里直接附上代码:

    // KMP算法主体逻辑。str是主串,pattern是模式串
    public static int kmp(String str, String pattern) {
    //预处理,生成next数组
    int[] next = getNexts(pattern);
    int j = 0;
    //主循环,遍历主串字符
    for (int i = 0; i < str.length(); i++) {
    while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
    //遇到坏字符时,查询next数组并改变模式串的起点
                j = next[j];
    }
    if (str.charAt(i) == pattern.charAt(j)) {
                j++;
    }
    if (j == pattern.length()) {
    //匹配成功,返回下标
    return i - pattern.length() + 1;
    }
    }
    return -1;
    }
    
    
    // 生成Next数组
    private static int[] getNexts(String pattern) {
    int[] next = new int[pattern.length()];
    int j = 0;
    for (int i=2; i<pattern.length(); i++) {
    while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
    //从next[i+1]的求解回溯到 next[j]
                j = next[j];
    }
    if (pattern.charAt(j) == pattern.charAt(i-1)) {
                j++;
    }
    next[i] = j;
    }
    return next;
    }
    
    public static void main(String[] args) {
    String str = "ATGTGAGCTGGTGTGTGCFAA";
    String pattern = "GTGTGCF";
    int index = kmp(str, pattern);
    System.out.println("首次出现位置:" + index);
    }
    
    更多相关内容
  • 首先对三种基本字符串匹配算法进行了详细分析和说明,再编程实现。创新拓展研究了Boyer-Moore算法,进行了分析和编程实现。让四种算法对数据量极大的文本,进行子串的查询处理,并分析算法运行时间效率,并对所有...
  • 7.1 字符阵列 7.2 字符串单元阵列 7.3 字符串比较 7.4 字符串搜索与取代 7.5 字符串与数值之间的变换 7.6 综合设计示例 7.7 字符串函数 配套一些小程序
  • vc++ 带通配符的字符串匹配算法实例源代码,用"*" 和 "?"进行字符串的匹配查找。直接拷贝代码就能使用。部分函数功能:带通配符的字符串匹配  参数:lpszSour是一个普通字符串;  lpszMatch是一可以包含通配符的...
  • 主要介绍了php中最简单的字符串匹配算法,可实现简单的字符串查找与匹配位置显示功能,是比较实用的字符串操作技巧,需要的朋友可以参考下
  • 字符串匹配算法之Sunday算法C++实现
  • 主要介绍了Python字符串匹配算法KMP实现方法,实例分析了Python针对字符串操作的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 主要介绍了Python实现字符串匹配算法代码示例,涉及字符串匹配存在的问题,蛮力法字符串匹配,Horspool算法,具有一定参考价值,需要的朋友可以了解下。
  • 字符串的模式匹配应用十分广泛,在信息的搜索查询等方面具有重要作用,研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法...
  • 如何用KMP字符串匹配算法求出主串中所包含模式串的总个数 #include using namespace std; void getnext(int next[],string s,int len) { int j=0,k=-1; next[0]=-1; while(j<len){ if(k==-1||s[j]==s[k]){ j...
  • 字符串匹配算法详解

    千次阅读 多人点赞 2020-12-29 20:21:00
    解决上面问题的算法我们称之为字符串匹配算法,今天我们来介绍三种字符串匹配算法,大家记得打卡呀,说不准面试的时候就问到啦。 BF算法(Brute Force) 这个算法很容易理解,就是我们将模式串和主串进行比较,一致...

    希望看到文章的你们,能够在今年的研究生考试中超常发挥。

    愿你们都能考上自己心仪的学校,为你们的备考生涯划上一个完美的句号。做为你们的师兄有几句话想对你们说,希望这些话能对你们有一些帮助。

    马上就要考试了,不要再继续啃难题了,看一些自己做过的题,曾经做错的题。因为我认为这个时候做难题,会比较打击自信心。考研的前一天我对自己十分有信心,但是不知道那天抽什么疯,做了一套特别难的数学模拟题,果不其然做的一塌糊涂,因为这套题让我怀疑自身实力,影响了考试心态。

    不要放弃!无论考场上发生什么,也不要放弃,保持平常心,完成所有考试,当时我考外语的时候就感觉发挥极差,甚至有点不想去参加下面的考试,如果当时我没有参加剩下的考试,肯定就考不上了。所以一定一定要完成所有考试。

    愿你们都能够成功上岸,你们真的很不容易,加油,必胜!另外咱们的文章视频中有送给你们的小彩蛋,大家快去看呀。

    为保证代码严谨性,文中所有代码均在 leetcode 刷题网站 AC ,大家可以放心食用。

    皇上生辰之际,举国同庆,袁记菜馆作为天下第一饭店,所以被选为这次庆典的菜品供应方,这次庆典对于袁记菜馆是一项前所未有的挑战,毕竟是第一次给皇上庆祝生辰,稍有不慎就是掉脑袋的大罪,整个袁记菜馆内都在紧张的布置着。此时突然有一个店小二慌慌张张跑到袁厨面前汇报,到底发生了什么事,让店小二如此慌张呢?

    袁记菜馆内

    店小二:不好了不好了,掌柜的,出大事了。

    袁厨:发生什么事了,慢慢说,如此慌张,成何体统。(开店开久了,架子出来了哈)

    店小二:皇上按照咱们菜单点了 666 道菜,但是咱们做西湖醋鱼的师傅请假回家结婚了,不知道皇上有没有点这道菜,如果点了这道菜,咱们做不出来,那咱们店可就完了啊。

    (袁厨听了之后,吓得一屁股坐地上了,缓了半天说道)

    袁厨:别说那么多了,快给我找找皇上点的菜里面,有没有这道菜!

    找了很久,并且核对了很多遍,最后确认皇上没有点这道菜。菜馆内的人都松了一口气

    通过上面的一个例子,让我们简单了解了字符串匹配,下面我们一起来详细了解一下吧。

    字符串匹配:设 S 和 T 是给定的两个串,在主串 S 中找到模式串 T 的过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现的位置,否则匹配不成功,返回  -1。

    例:

    在上图中,我们试图找到模式串 T = baab,在主串 S = abcabaabcabac 中第一次出现的位置,即为红色阴影部分, T 第一次在 S 中出现的位置下标为 4 ( 字符串的首位下标是 0 ),所以返回 4。如果模式串 T 没有在主串 S 中出现,则返回 -1。

    解决上面问题的算法我们称之为字符串匹配算法,今天我们来介绍三种字符串匹配算法,大家记得打卡呀,说不准面试的时候就问到啦。

    BF算法(Brute Force)

    这个算法很容易理解,就是我们将模式串和主串进行比较,一致时则继续比较下一字符,直到比较完整个模式串。不一致时则将模式串后移一位,重新从模式串的首位开始对比,重复刚才的步骤下面我们看下这个方法的动图解析,看完肯定一下就能搞懂啦。

    通过上面的代码是不是一下就将这个算法搞懂啦,下面我们用这个算法来解决下面这个经典题目吧。

    leetcdoe 28. 实现 strStr()

    题目描述

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

    示例 1:

    输入: haystack = "hello", needle = "ll" 输出: 2

    示例 2:

    输入: haystack = "aaaaa", needle = "bba" 输出: -1

    题目解析

    其实这个题目很容易理解,但是我们需要注意的是一下几点,比如我们的模式串为 0 时,应该返回什么,我们的模式串长度大于主串长度时,应该返回什么,也是我们需要注意的地方。下面我们来看一下题目代码吧。

    题目代码

    我们看一下BF算法的另一种算法(显示回退),其实原理一样,就是对代码进行了一下修改,只要看完咱们的动图,这个也能够一下就能看懂,大家可以结合下面代码中的注释和动图进行理解。

    BM算法(Boyer-Moore)

    我们刚才说过了 BF 算法,但是 BF 算法是有缺陷的,比如我们下面这种情况

    如上图所示,如果我们利用 BF 算法,遇到不匹配字符时,每次右移一位模式串,再重新从头进行匹配,我们观察一下,我们的模式串 abcdex 中每个字符都不一样,但是我们第一次进行字符串匹配时,abcde 都匹配成功,到 x 时失败,又因为模式串每位都不相同,所以我们不需要再每次右移一位,再重新比较,我们可以直接跳过某些步骤。如下图

    我们可以跳过其中某些步骤,直接到下面这个步骤。那我们是依据什么原则呢?

    坏字符规则

    我们之前的 BF 算法是从前往后进行比较 ,BM 算法是从后往前进行比较,我们来看一下具体过程,我们还是利用上面的例子。

    BM 算法是从后往前进行比较,此时我们发现比较的第一个字符就不匹配,我们将主串这个字符称之为坏字符,也就是 f ,我们发现坏字符之后,模式串 T 中查找是否含有该字符 f,我们发现并不存在 f,此时我们只需将模式串右移到坏字符的后面一位即可。如下图

    那我们在模式串中找到坏字符该怎么办呢?见下图

    此时我们的坏字符为 f , 我们在模式串中,查找发现含有坏字符  f ,我们则需要移动模式串 T ,将模式串中的 f 和坏字符对齐。见下图。

    然后我们继续从右往左进行比较,发现 d 为坏字符,则需要将模式串中的 d 和坏字符对齐。

    那么我们在来思考一下这种情况,那就是模式串中含有多个坏字符怎么办呢?

    那么我们为什么要让最靠右的对应元素与坏字符匹配呢?如果上面的例子我们没有按照这条规则看下会产生什么问题。

    如果没有按照我们上述规则,则会漏掉我们的真正匹配。我们的主串中是含有 babac 的,但是却没有匹配成功,所以应该遵守最靠右的对应字符与坏字符相对的规则。

    我们上面一共介绍了三种移动情况,分别是下方的模式串中没有发现与坏字符对应的字符,发现一个对应字符,发现两个。这三种情况我们分别移动不同的位数,那我们是根据依据什么来决定移动位数的呢?下面我们给图中的字符加上下标。见下图

    下面我们来考虑一下这种情况。

    此时这种情况肯定是不行的,不往右移动,甚至还有可能左移,那么我们有没有什么办法解决这个问题呢?继续往下看吧。

    好后缀规则

    好后缀其实也很容易理解,我们之前说过 BM 算法是从右往左进行比较,下面我们来看下面这个例子。

    这里如果我们按照坏字符进行移动是不合理的,这时我们可以使用好后缀规则,那么什么是好后缀呢?

    BM 算法是从右往左进行比较,发现坏字符的时候此时 cac  已经匹配成功,在红色阴影处发现坏字符。此时已经匹配成功的  cac 则为我们的好后缀,此时我们拿它在模式串中查找,如果找到了另一个和好后缀相匹配的串,那我们就将另一个和好后缀相匹配的串 ,滑到和好后缀对齐的位置。

    是不是感觉有点拗口,没关系,我们看下图,红色代表坏字符,绿色代表好后缀

    上面那种情况搞懂了,但是我们思考一下下面这种情况

    上面我们说到了,如果在模式串的头部没有发现好后缀,发现好后缀的子串也可以。但是为什么要强调这个头部呢?

    我们下面来看一下这种情况

    但是当我们在头部发现好后缀的子串时,是什么情况呢?

    下面我们通过动图来看一下某一例子的具体的执行过程

    说到这里,坏字符和好后缀规则就算说完了,坏字符很容易理解,我们对好后缀总结一下

    1.如果模式串含有好后缀,无论是中间还是头部可以按照规则进行移动。如果好后缀在模式串中出现多次,则以最右侧的好后缀为基准。

    2.如果模式串头部含有好后缀子串则可以按照规则进行移动,中间部分含有好后缀子串则不可以。

    3.如果在模式串尾部就出现不匹配的情况,即不存在好后缀时,则根据坏字符进行移动,这里有挺多文章没有提到,是个需要特别注意的地方,我是在这个论文里找到答案的,感兴趣的同学可以看下。

    Boyer R S,Moore J S. A fast string searching algorithm[J]. Communications of the ACM,1977,10:762-772.

    之前我们刚开始说坏字符的时候,是不是有可能会出现负值的情况,即往左移动的情况,所以我们为了解决这个问题,我们可以分别计算好后缀和坏字符往后滑动的位数(好后缀存在时),然后取两个数中最大的,作为模式串往后滑动的位数。

    这破图画起来是真费劲啊。下面我们来看一下算法代码,代码有点长,我都标上了注释也在网站上 AC 了,如果各位感兴趣可以看一下,不感兴趣的话,理解坏字符和好后缀规则即可。可以直接跳到 KMP 部分

    我们来理解一下我们代码中用到的两个数组,因为两个规则的移动位数,只与模式串有关,与主串无关,所以我们可以提前求出每种情况的移动情况,保存到数组中。

    KMP算法(Knuth-Morris-Pratt)

    我们刚才讲了 BM 算法,虽然不是特别容易理解,但是如果你用心看的话肯定可以看懂的,我们再来看一个新的算法,这个算法是考研时必考的算法。实际上 BM 和 KMP 算法的本质是一样的,你理解了 BM 再来理解 KMP 那就是分分钟的事啦。

    我们先来看一个实例

    注:为了让读者更容易理解,我们将指针移动改成了模式串移动,两者相对与主串的移动是一致的,重新比较时都是从指针位置继续比较。

    通过上面的实例是不是很快就能理解 KMP 算法的思想了,我们继续往下看。

    在上面的例子中我们提到了一个名词,最长公共前后缀,这个是什么意思呢?下面我们通过一个较简单的例子进行描述。

    此时我们在红色阴影处匹配失败,绿色为匹配成功部分,则我们观察匹配成功的部分。

    我们来看一下匹配成功部分的所有前后缀

    我们的最长公共前后缀如下图,则我们需要这样移动

    好啦,看完上面的图,KMP的核心原理已经基本搞定了,但是我们现在的问题是,我们应该怎么才能知道他的最长公共前后缀的长度是多少呢?怎么知道移动多少位呢?

    刚才我们在 BM 中说到,我们移动位数跟主串无关,只跟模式串有关,跟我们的 bc,suffix,prefix 数组的值有关,我们通过这些数组就可以知道我们每次移动多少位啦,其实 KMP 也有一个数组,这个数组叫做 next 数组,那么这个 next 数组存的是什么呢?

    next 数组存的咱们最长公共前后缀中,前缀的结尾字符下标。是不是感觉有点别扭,我们通过一个例子进行说明。

    我们知道 next 数组之后,我们的 KMP 算法实现起来就很容易啦,另外我们看一下 next 数组到底是干什么用的。

    剩下的就不用说啦,完全一致啦,咱们将上面这个例子,翻译成和咱们开头对应的动画大家看一下。

    下面我们看一下代码,标有详细注释,大家认真看呀。

    注:很多教科书的 next 数组表示方式不一致,理解即可

    好啦好啦先就写这么多吧,累屁了,剩下的几种就先不写了,觉得这个文章对你有帮助的话,欢迎各位点赞,评论,在看,转发。哦,我还没评论功能。哈哈

    往期精选

    我是袁厨,一个酷爱用动图解算法的年轻人,一个酷爱做饭的程序员,一个想和你一起进步的小老弟。

    展开全文
  • BM算法 c语言实现 详细注解 高手作品
  • 32|字符串匹配基础上如何借助哈希算法实现高效字符串匹配 32|字符串匹配基础上如何借助哈希算法实现高效字符串匹配 从今天开始我们来学习字符串匹配算法字符串匹配这样一个功能我想对于任何一个开发工程师来说应该都...
  • 字符串匹配算法ppt

    2016-11-04 17:45:14
    常见的字符串匹配算法及实现
  • kmp 字符串匹配 算法 C语言实现 函数
  • 字符串匹配算法知多少?

    千次阅读 多人点赞 2021-07-03 10:00:09
    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢? 想到是很正常的,谁让它那么优秀呢。 BF算法 不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法...

    在这里插入图片描述

    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢?

    想到是很正常的,谁让它那么优秀呢。


    BF算法

    不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法。

    能想明白了吧。

    如果模式串长度为 m,主串长度为 n,那在主串中,就会有 n-m+1 个长度为 m 的子串,我们只需要暴力地对比这 n-m+1 个子串与模式串,就可以找出主串与模式串匹配的子串。

    1、从头开始往后遍历匹配;
    2、遇上不对了,就回头,把子串和主串的匹配头后移一位
    3、重复以上。直到找到或确定找不到。
    

    复杂度很高啊,但是在实际开发中也是比较常用的。为什么呢?
    真当天天都有成千上万个字符的主串让我们去匹配吗?一般都比较短,而且,统计意义上,算法执行效率不会真的到M*N的地步。

    理论还是要结合实际的。

    还有另一个原因,就是它好写。当然kmp现在更好写,因为封装好了。
    我说的是类似的场景,没有封装好的函数时候,好写,好改。


    RK算法

    RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题,后面我们会讲到)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了。

    有没有方法可以提高哈希算法计算子串哈希值的效率呢?

    我们假设要匹配的字符串的字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串的哈希值。

    比如要处理的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。我们把 a~z 这 26 个字符映射到 0~25 这 26 个数字,a 就表示 0,b 就表示 1,以此类推,z 表示 25。

    在这里插入图片描述

    这里有一个小细节需要注意,那就是 26^(m-1) 这部分的计算,我们可以通过查表的方法来提高效率。我们事先计算好 26^0、26^1、26^2……26^(m-1),并且存储在一个长度为 m 的数组中

    模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1),总共需要比较 n-m+1 个子串的哈希值,所以,这部分的时间复杂度也是 O(n)。所以,RK 算法整体的时间复杂度就是 O(n)。

    但是呢,还有一个很致命的问题,叫做数值过大。
    以幂增的速度是非常快的,用不了多久int就hold不住了啊,那要怎么办?难道我们前面所做的努力都白费了?

    其实不然。
    比方说我们可以改乘为加,当我们匹配到一样的哈希值的时候,再打开子串进行比对,因为相加的话是会有哈西冲突的。

    此外,我们还可以加点优化,一边对主串构建,一边对子串进行匹配,如果一样的话就不继续计算后面的hash了。
    该省的时候就要省,该花的时候就要花。


    编辑器中的全局替换方法:BM算法

    用过吗?比方说要在我这篇博客里找出全部的“主串”这个词,有没有想过其底层的原理?

    这是一个性能优于KMP的算法。

    坏字符

    BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。

    我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符(主串中的字符)

    在这里插入图片描述

    这时候该如何操作呢?我们去子串中寻找这个坏字符,如果找到了,就让两个字符的位置对上,继续往后,如果没有找到,就将整个子串移动到坏字符后面。

    很显然,这会儿没找到。

    在这里插入图片描述

    接下来该怎么滑呢?又是个坏字符。
    但是在子串中找到了那个坏字符,那就将两个字符的位置对上。

    在这里插入图片描述

    模式串中有对应的坏字符时,让模式串中 最靠右 的对应字符与坏字符相对。

    在这里插入图片描述

    但是呢,用这个规则还是不太够用的,有些个特殊情况吧,它会导致不但不会向后滑动模式串,还有可能会倒推、

    比如说主串:kkkkkkkkkkkkkkkkkk,模式串是 akk


    好后缀规则

    在这里插入图片描述

    如果模式串中存在已经匹配成功的好后缀,则把目标串与好后缀对齐,然后从模式串的最尾元素开始往前匹配。

    在这里插入图片描述

    如果无法找到匹配好的后缀,找一个匹配的最长的前缀,让目标串与最长的前缀对齐:
    在这里插入图片描述

    在这里插入图片描述

    如果完全不存在和好后缀匹配的子串,则右移整个模式串


    代码实现

    难顶,我一定会回来的

    // a,b 表示主串和模式串;n,m 表示主串和模式串的长度。
    public int bm(char[] a, int n, char[] b, int m) {
      int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
      generateBC(b, m, bc); // 构建坏字符哈希表
      int[] suffix = new int[m];
      boolean[] prefix = new boolean[m];
      generateGS(b, m, suffix, prefix);
      int i = 0; // j 表示主串与模式串匹配的第一个字符
      while (i <= n - m) {
        int j;
        for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
          if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
        }
        if (j < 0) {
          return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
        }
        int x = j - bc[(int)a[i+j]];
        int y = 0;
        if (j < m-1) { // 如果有好后缀的话
          y = moveByGS(j, m, suffix, prefix);
        }
        i = i + Math.max(x, y);
      }
      return -1;
    }
     
    // j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
      int k = m - 1 - j; // 好后缀长度
      if (suffix[k] != -1) return j - suffix[k] +1;
      for (int r = j+2; r <= m-1; ++r) {
        if (prefix[m-r] == true) {
          return r;
        }
      }
      return m;
    }
    

    KMP算法

    【C++】算法集锦(10)通俗讲kmp算法

    展开全文
  • 字符串匹配算法综述

    万次阅读 多人点赞 2018-07-22 21:39:23
    字符串匹配算法综述 字符串匹配算法综述:BF、RK、KMP、BM、Sunday 字符串匹配算法,是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目。此算法通常输入为原字符串(string)和子串(pattern),要求...

    字符串匹配算法综述

    字符串匹配算法综述:BF、RK、KMP、BM、Sunday

    字符串匹配算法,是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目。此算法通常输入为原字符串(string)和子串(pattern),要求返回子串在原字符串中首次出现的位置。比如原字符串为“ABCDEFG”,子串为“DEF”,则算法返回3。常见的算法包括:BF(Brute Force,暴力检索)、RK(Robin-Karp,哈希检索)、KMP(教科书上最常见算法)、BM(Boyer Moore)、Sunday等,下面详细介绍。

    1 BF算法:

    暴力检索法是最好想到的算法,也最好实现,在情况简单的情况下可以直接使用:

    这里写图片描述
    首先将原字符串和子串左端对齐,逐一比较;如果第一个字符不能匹配,则子串向后移动一位继续比较;如果第一个字符匹配,则继续比较后续字符,直至全部匹配。
    时间复杂度:O(MN)

    2 RK算法:

    RK算法是对BF算法的一个改进:在BF算法中,每一个字符都需要进行比较,并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中,就尝试只进行一次比较来判定两者是否相等。
    RK算法也可以进行多模式匹配,在论文查重等实际应用中一般都是使用此算法。
    这里写图片描述
    首先计算子串的HASH值,之后分别取原字符串中子串长度的字符串计算HASH值,比较两者是否相等:如果HASH值不同,则两者必定不匹配,如果相同,由于哈希冲突存在,也需要按照BF算法再次判定。
    按照此例子,首先计算子串“DEF”HASH值为Hd,之后从原字符串中依次取长度为3的字符串“ABC”、“BCD”、“CDE”、“DEF”计算HASH值,分别为Ha、Hb、Hc、Hd,当Hd相等时,仍然要比较一次子串“DEF”和原字符串“DEF”是否一致。
    时间复杂度:O(MN)(实际应用中往往较快,期望时间为O(M+N))

    3 KMP算法:

    字符串匹配最经典算法之一,各大教科书上的看家绝学,曾被投票选为当今世界最伟大的十大算法之一;但是晦涩难懂,并且十分难以实现,希望我下面的讲解能让你理解这个算法。
    KMP算法在开始的时候,也是将原字符串和子串左端对齐,逐一比较,但是当出现不匹配的字符时,KMP算法不是向BF算法那样向后移动一位,而是按照事先计算好的“部分匹配表”中记载的位数来移动,节省了大量时间。这里我借用一下阮一峰大神的例子来讲解:
    这里写图片描述
    首先,原字符串和子串左端对齐,比较第一个字符,发现不相等,子串向后移动,直到子串的第一个字符能和原字符串匹配。
    这里写图片描述
    当A匹配上之后,接着匹配后续的字符,直至原字符串和子串出现不相等的字符为止。
    这里写图片描述
    此时如果按照BF算法计算,是将子串整体向后移动一位接着从头比较;按照KMP算法的思想,既然已经比较过了“ABCDAB”,就要利用这个信息;所以针对子串,计算出了“部分匹配表”如下(具体如何计算后面会说,这个先介绍整个流程):
    这里写图片描述
    刚才已经匹配的位数为6,最后一个匹配的字符为“B”,查表得知“B”对应的部分匹配值为2,那么移动的位数按照如下公式计算:
    移动位数 = 已匹配的位数 - 最后一个匹配字符的部分匹配值
    那么6 - 2 = 4,子串向后移动4位,到下面这张图:
    这里写图片描述
    因为空格和“C”不匹配,已匹配位数为2,“B”对应部分匹配值为0,所以子串向后移动2-0=2位。
    这里写图片描述
    空格和“A”不匹配,已匹配位数为0,子串向后移动一位。
    这里写图片描述
    逐个比较,直到发现“C”与“D”不匹配,已匹配位数为6,“B”对应部分匹配值为2,6-2=4,子串向后移动4位。
    这里写图片描述
    逐个比较,直到全部匹配,返回结果。
    下面说明一下“部分匹配表”如何计算,“部分匹配值”是指字符串前缀和后缀所共有元素的长度。前缀是指除最后一个字符外,一个字符串全部头部组合;后缀是指除第一个字符外,一个字符串全部尾部组合。以”ABCDABD”为例:
    “AB”的前缀为[A],后缀为[B],共有元素的长度为0;
    “ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
    “ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
    “ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;
    “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;
    “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。
    在计算“部分匹配表”时,一般使用DP(动态规划)算法来计算(表示为next数组)://这里我没看懂,理论上不用DP直接搜也行啊

            int* next = new int[needle.length()];
            next[0] = 0;
            int k = 0;
            for (int i = 1; i < needle.length(); i++)
            {
                while (k > 0 && needle[i] != needle[k])
                {
                    k = next[k - 1];
                }
                if (needle[i] == needle[k])
                {
                    k++;
                }
                next[i] = k;
            }

    时间复杂度:O(N)

    4 BM算法:

    在本科的时候,我一直认为KMP算法是最好的字符串匹配算法,直到后来我遇到了BM算法。BM算法的执行效率要比KMP算法快3-5倍左右,并且十分容易理解。各种记事本的“查找”功能(CTRL + F)一般都是采用的此算法。
    网上所有讲述这个算法的帖子都是以传统的“好字符规则”和“坏字符规则”来讲述的,但是个人感觉其实这样不容易理解,我总结了另外一套简单的算法规则:
    我们拿这个算法的发明人Moore教授的例子来讲解:
    这里写图片描述
    首先,原字符串和子串左端对齐,但是从尾部开始比较,就是首先比较“S”和“E”,这是一个十分巧妙的做法,如果字符串不匹配的话,只需要这一次比较就可以确定。
    在BM算法中,当每次发现当前字符不匹配的时候,我们就需要寻找一下子串中是否有这个字符;比如当前“S”和“E”不匹配,那我们需要寻找一下子串当中是否存在“S”。发现子串当中并不存在,那我们将子串整体向后移动到原字符串中“S”的下一个位置(但是如果子串中存在原字符串当前字符肿么办呢,我们后面再说):
    这里写图片描述
    我们接着从尾部开始比较,发现“P”和“E”不匹配,那我们查找一下子串当中是否存在“P”,发现存在,那我们就把子串移动到两个“P”对齐的位置:
    这里写图片描述
    已然从尾部开始比较,“E”匹配,“L”匹配,“P”匹配,“M”匹配,“I”和“A”不匹配!那我们就接着寻找一下子串当前是否出现了原字符串中的字符,我们发现子串中第一个“E”和原字符串中的字符可以对应,那直接将子串移动到两个“E”对应的位置:
    这里写图片描述
    接着从尾部比较,发现“P”和“E”不匹配,那么检查一下子串当中是否出现了“P”,发现存在,那么移动子串到两个“P”对应:
    这里写图片描述
    从尾部开始,逐个匹配,发现全部能匹配上,匹配成功~
    时间复杂度:最差情况O(MN),最好情况O(N)

    5 Sunday算法:

    后来,我又发现了一种比BM算法还要快,而且更容易理解的算法,就是这个Sunday算法:
    这里写图片描述
    首先原字符串和子串左端对齐,发现“T”与“E”不匹配之后,检测原字符串中下一个字符(在这个例子中是“IS”后面的那个空格)是否在子串中出现,如果出现移动子串将两者对齐,如果没有出现则直接将子串移动到下一个位置。这里空格没有在子串中出现,移动子串到空格的下一个位置“A”:
    这里写图片描述
    发现“A”与“E”不匹配,但是原字符串中下一个字符“E”在子串中出现了,第一个字符和最后一个字符都有出现,那么首先移动子串靠后的字符与原字符串对齐:
    这里写图片描述
    发现空格和“E”不匹配,原字符串中下一个字符“空格”也没有在子串中出现,所以直接移动子串到空格的下一个字符“E”:
    这里写图片描述
    这样从头开始逐个匹配,匹配成功!
    时间复杂度:最差情况O(MN),最好情况O(N)

    //实际我写好像可以是o(M+N)啊。。

    代码粘一下:

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    char a[10005],b[10005];//long a>long b
    int c[30];//表示b串中存在的字母;不存在则为1,存在为最靠后的此字符距离尾部加一(要跳的地方) 
    int la,lb;//字符串a,b的长度 
    int head;//当前搜索到的头字符 
    int main()
    {
        scanf("%s",a);
        scanf("%s",b);//read in
        la=strlen(a);
        lb=strlen(b); 
        for(int i=0;i<=lb-1;i++)
            c[b[i]-'a'+1]=lb-i;//初始化c数组 
        for(int i=0;head<=la-1;)//i表示当前匹配长度 ,head指针跳到a尾时结束 
        {
            if(a[head+i]==b[i])
            {
                i++;//匹配则更新i值
                if(i==lb) //匹配到的长度等于b串长度 则成功 
                {
                    printf("Yes");return 0;
                }
            }        
            else
            {
                if(c[a[head+lb]-'a'+1]!=0) head=head+c[a[head+lb]-'a'+1];//判断是否出现
                else head=head+lb+2; //未出现,跳到下一个长度 
                i=0;//匹配值更新为0
            }         
        }
        printf("No");
        return 0;
    }
    展开全文
  • 内容索引:VC/C++源码,字符处理,通配符,算法 vc++ 带通配符的字符串匹配算法实例源代码,用"*" 和 "?"进行字符串的匹配查找。直接拷贝代码就能使用。部分函数功能:带通配符的字符串匹配  参数:lpszSour是一个普通...
  • Aho-Corasick(AC)算法是一种广泛使用的多字符串匹配算法。 在本文中,我们提出了一种基于节点分组的交流自动机的空间压缩方法,并使用CUDA(计算机统一设备架构)在GPU平台上实现了交流算法。 在我们进行的几次...
  • 字符串匹配算法之暴力做法(朴素算法)
  • 主要介绍了多模字符串匹配算法原理及Java实现代码,涉及算法背景,原理,构建过程简单介绍几Java代码实现等相关内容,具有一定参考价值,需要的朋友可以了解下。
  • BM字符串匹配算法.zip

    2021-11-12 12:53:35
    字符串匹配算法,优化后可以删除匹配的所有模式字符串
  • 字符串匹配算法-最全

    2020-09-28 21:01:09
    字符串匹配算法-最全一、常用字符串匹配算法及其简介二、算法实现及解析算法解决问题点1、BF算法(时间复杂度O(mn))2、RK算法(时间复杂度O(n))3、BM算法4、KMP算法 一、常用字符串匹配算法及其简介 BF算法、RK算法,...
  • 在 Java 里用的是indexOf函数,其底层就是字符串匹配算法。主要分类如下: 单模式与多模式的区别 单模式匹配算法即在一段文本中匹配单个字符串,多模式匹配算法则是需要匹配多个字符串。 单模式匹配算法 ...
  • 该项目是一个 C# 包装器和一组 SQL Server 安装脚本,用于使 SimMetrics 字符串匹配算法在可用。 SimMetrics 最初是在发布的。 该项目使用该库的 1.5 版。 后续版本已迁移到Java。 C#包装器受此启发 提供了支持的...
  • 主要介绍了PHP实现的字符串匹配算法,简单描述了sunday算法的概念与原理,并结合实例形式分析了php基于sunday算法实现字符串匹配操作相关技巧,需要的朋友可以参考下
  • 字符串匹配算法(BM)

    万次阅读 多人点赞 2019-06-22 04:12:15
    文章目录1. BM(Boyer-Moore)算法 1. BM(Boyer-Moore)算法 思想:有模式中不存在的字符,那么肯定不匹配,往后多移动几位,提高效率 BM原理:坏字符规则,好后缀规则 ...
  • 字符串匹配算法之KMP算法(图例详解)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 218,565
精华内容 87,426
关键字:

字符串匹配算法