精华内容
参与话题
问答
  • 字符串匹配

    千次阅读 2019-06-27 19:44:14
    字符串A中查找字符串B,那字符串A就是主串,字符串B就是模式串。 我们把主串的长度记作n,模式串的长度记作m。因为我们是在主串中查找模式串,所以n>m。 几种单模式串匹配算法 BF(暴力)算法 RK算法 BM算法 ...

    基础概念

    • 字符串匹配
      在日常操作电脑中,经常用到查找操作。这里用到很重要的概念就是字符串匹配,所谓字符串匹配就是在主串中搜索模式串是否存在及其存在的位置。
    • 主串模式串
      在字符串A中查找字符串B,那字符串A就是主串,字符串B就是模式串。
      我们把主串的长度记作n,模式串的长度记作m。因为我们是在主串中查找模式串,所以n>m。

    几种单模式串匹配算法

    1. BF(暴力)算法
    2. RK算法
    3. BM算法
    4. KMP算法

    1. BF(Brute Force)算法

    在这里插入图片描述
    时间复杂度O(n*m),其中n是主串长度,m是模式串长度。
    缺陷:忽略了已检测过的文本信息。

    2. RK(Rabin-Karp)算法

    如果模式串长度为m,主串长度为n,那在主串中,就会有n-m+1个长度为m的子串。
    BF算法需要对比n-m+1次,每次对比都需要依次对比m个字符。

    RK算法的思路是:

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

    在这里插入图片描述
    简单的哈希算法,需要遍历子串的每个字符,尽管模式串与子串比较的效率提高了,但是,算法整体的效率并没有提高。

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

    假设字符串中只包含a~z这26个小写字符,我们用二十六进制来表示一个字符串,对 应的哈希值就是二十六进制数转化成十进制的结果。
    在这里插入图片描述
    这种哈希算法有一个特点,在主串中,相邻两个子串的哈希值的计算公式有一定关系。
    在这里插入图片描述
    相邻两个子串s[i-1]和s[i] (i表示子串在主串中的起始位置,子串的长度都为m)。我们可以使用s[i-1]的哈希值很快的计算出s[i]的哈希值。
    在这里插入图片描述
    h[i] = (h[i-1] - 26^(m-1)*(s[i-1]-‘a’)) * 26 + (s[i+m-1] - ‘a’)

    可以提前计算26^(m-1)这部分的值,然后通过查表的方式提高效率。
    在这里插入图片描述
    RK算法包含两部分,计算子串哈希值和模式串哈希值与子串哈希值之间的比较。

    • 第一部分,我们前面也分析了,可以通过设计特殊的哈希算法,只需要扫描一遍主串就能计算出所有子串的哈希值了,所以这部分的时间复杂度是O(n)。
    • 第二部分,模式串哈希值与每个子串哈希值之间的比较的时间复杂度是O(1),总共需要比较n-m+1个子串的哈希值,所以,这部分的时间复杂度也是O(n)。

    所以,RK算法整体的时间复杂度就是O(n)。

    如上这种哈希算法是不会有哈希冲突的,因为我们是基于进制来表示一个字符串的,也就是说,一个字符串与一个二十六进制数一一对应,不同的字符串的哈希值肯定不一样。

    问题:模式串很长,相应的主串中的子串也会很长,通过上面的哈希算法计算得到的哈希值就可能很大,可能会超过了计算机中整型数据可以表示的范围。

    建议:设计数值较小的哈希函数,可能会有哈希冲突。在哈希值相等时,还需再对比一下子串和模式串本身。

    3. BM(Boyer-Moore)算法

    我们把模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF算法和RK算法的做法是,模式串往后滑动一位,然后从模式 串的第一个字符开始重新匹配。
    在这里插入图片描述
    在这个例子里,主串中的c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要c与模式串有重合,肯定无法匹配。所以,我们可以一次性把模式串往 后多滑动几位,把模式串移动到c的后面。
    在这里插入图片描述
    字符串匹配的关键,就是模式串的如何移动最高效。

    BM算法本质上就是寻找一种规律,使得模式串和主串匹配过程中,当遇到字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串尽量往后多滑动几位。

    BM算法包含两部分

    • 坏字符规则(bad character rule)
    • 好后缀规则(good suffix rule)

    BM算法模式串的匹配方式是从末尾往前倒着匹配。
    在这里插入图片描述

    坏字符规则

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

    • 坏字符c在模式串不存在,这个时候,我们可以将模式串直接往后滑动三(模式串长度)位,将模式串滑动到c后面的位置,再从模式串的末尾字符开始比较。
      在这里插入图片描述
    • 坏字符a在模式串中存在,模式串中下标是0的位置也是字符a。这种情况下,我们可以将模式串往后滑动两位,让两个a上下对齐,然后再从模式串的末尾字符开 始,重新匹配。
      在这里插入图片描述
    • 规律:当发生不匹配的时候,我们把坏字符对应的模式串中的字符下标记作si。如果坏字符在模式串中存在,我们把这个坏字符在模式串中的下标记作xi。如果不存在, 我们把xi记作-1。那模式串往后移动的位数就等于si-xi。(注意,我这里说的下标,都是字符在模式串的下标)
      在这里插入图片描述
    • 若xi有多个,选择下标最大的那个,即最靠后的那个。

    利用坏字符规则,BM算法在最好情况下的时间复杂度非常低,是O(n/m)。

    • 比如,主串是aaabaaabaaabaaab,模式串是aaaa。每次比对,模式串都可以直接后移四位,所以,匹配具有类似特点的模式串和主串的时候,BM算法非常高效。

    • 不过,单纯使用坏字符规则还是不够的。因为根据si-xi计算出来的移动位数,有可能是负数,比如主串是aaaaaaaaaaaaaaaa,模式串是baaa。不但不会向后滑动模式串,还有可能倒退。所以,BM算法还需要用到“好后缀规则”。

    好后缀规则

    在这里插入图片描述
    我们把已经匹配的bc叫作好后缀,记作{u}。我们拿它在模式串中查找,如果找到了另一个跟{u}相匹配的子串{u*},那我们就将模式串滑动到子串{u*}与主串 中{u}对齐的位置。
    在这里插入图片描述

    • 若在模式串中找不到另一个等于{u}的子串,我们就直接将模式串,滑动到主串中{u}的后面,因为之前的任何一次往后滑动,都不可能匹配主串中{u}的情况。
      在这里插入图片描述
      当模式串中不存在等于{u}的子串时,直接将模式串滑动到主串{u}的后面。是否有点太过头呢?
      在这里插入图片描述
      如果好后缀在模式串中不存在可匹配的子串,那在我们一步一步往后滑动模式串的过程中。
    • 只要主串中的{u}与模式串有重合,那肯定就无法完全匹配。
    • 但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重合的部分相等的时候,就有可能会存在完全匹配的情况。
      在这里插入图片描述
      所以,在好后缀模式下,若模式串中找不到和好后缀完全匹配的子串,那么:
    • 先看好后缀在模式串中,是否有另一个匹配的子串
    • 还要考察好后缀的后缀子串,是否存在跟模式串的前缀子串匹配的。
      在这里插入图片描述
      BM算法会分别计算好后缀和坏字符往后滑动的位数,然后取两者中的大者,作为模式串往后滑动的位数。

    BM算法实现

    1.坏字符规则实现

    “坏字符规则”本身不难理解。当遇到坏字符时,要计算往后移动的位数si-xi,其中xi的计算是重点,我们如何求得xi呢?
    如果我们拿坏字符,在模式串中顺序遍历查找,这样就会比较低效,势必影响这个算法的性能。

    • 利用哈希表,将模式串中的每个字符及其下标都存到哈希表中

    假设字符集为256,每个字符大小为1个字节,可用大小为256的数组,记录每个字符在模式串中出现的位置,数组下标对应字符的ASCII码值,数组值为字符在模式串中的下标。
    在这里插入图片描述
    如上过程翻译成代码如下,其中变量b是模式串,m是模式串长度,bc是刚刚讲的哈希表:

    const SIZE int = 256
    
    func generateBC(b []byte, m int, bc []int) {
            for i := 0; i < SIZE; i++ {
                  bc[i] = -1//初始化bc
            }
            for i := 0; i < m; i++ {
                 ascii := int(b[i])//计算b[i]的asccii值
                 bc[ascii] = i
            }
    }
    

    在这里插入图片描述
    单有坏字符规则的BM算法,代码如下:

    func bm(mainStr, modeStr []byte) int {
    	bc := make([]int, SIZE)
    	n := len(mainStr)
    	m := len(modeStr)
    	generateBC(modeStr, m, bc) //构建坏字符哈希
    	i := 0                     //i表示主串与模式串对齐的第一个字符位置
    	for i <= n-m {
    		j := 0
    		for j = m - 1; j >= 0; j-- { //模式串从后往前匹配
    			if mainStr[i+j] != modeStr[j] {
    				break //坏字符对应模式串中的下标是j
    			}
    		}
    		if j < 0 {
    			return i //匹配成功,返回主串与模式串第一个匹配的字符的位置
    		}
    		moveNum := j - bc[int(mainStr[i+j])]
    		if moveNum <= 0 { //坏字符可能产生负数的移位
    			moveNum = 1
    		}
    		i = i + moveNum
    	}
    	return -1
    }
    

    好后缀规则实现

    回顾一下,前面讲过好后缀的处理规则中最核心的内容:

    • 在模式串中,查找跟好后缀匹配的另一个子串;
    • 在好后缀的后缀子串中,查找最长的、能跟模式串前缀子串匹配的后缀子串;

    若这两个操作直接使用“暴力”匹配,会使得BM算法效率不高。而好后缀也是模式串本身的后缀子串,所以在正式匹配之前,可以对模式串做预处理操作,预先计算好模式串中的每个后缀子串,对应的另一个可匹配子串的位置。
    在这里插入图片描述

    • 通过长度可以唯一确定一个后缀子串。

    现在引入suffx数组,数组下标k表示后缀子串的长度,下标对应的数组值表示,在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标位置。
    在这里插入图片描述

    • 若模式串中有多个(大于1个)子串跟后缀子串{u}匹配,那suffix数组中该存储模式串中最靠后的那个子串的起始位置,也就是下标最大的那个子串的起始位置。

    suffx数组可以解决好后缀在模式串中能找到另一个可匹配的情况,但是我们还要在好后缀的后缀子串中,查找最长的能跟模式串前缀子串匹配的后缀子串。

    • 用bool类型的prefix数组,来记录模式串的后缀子串是否能匹配模式串的前缀子串。
      在这里插入图片描述
    • 我们拿下标从0到i的子串(i可以是0到m-2)与整个模式串,求公共后缀子串。
    • 如果公共后缀子串的长度是k,那我们就记录suffix[k]=j(j表示公共后缀子串的起始下标)。
    • 如果j等于0,也就是说,公共后缀子串也是模式串的前缀子串,我们就记录prefix[k]=true。
      在这里插入图片描述
      把suffix数组和prefix数组的计算过程,用代码实现出来,如下所示:
    func generateGS(modeStr []byte, suffix []int, prefix []bool) {
    	m := len(modeStr)
    	for i := 0; i < m; i++ {
    		suffix[i] = -1    //默认是找不到和好后缀匹配的子串
    		prefix[i] = false //初始化
    	}
    	for i := 0; i < m-1; i++ { //modeStr[:i],即前缀子串
    		j := i
    		k := 0                                       //公共后缀子串长度
    		for j >= 0 && modeStr[j] == modeStr[m-k-1] { //与modeStr[:m-1]求公共后缀
    			j--
    			k++
    			suffix[k] = j + 1 //j+1表示公共后缀子串在modeStr[:i]中的起始下标,当有多个{u},suffix[k]会被后来者覆盖
    		}
    		if j == -1 {
    			prefix[k] = true //表示有和后缀子串匹配的前缀子串
    			//cabcabcab的suffix[3]=3,prefix[3]为true
    		}
    	}
    
    }
    

    有了这两个数组后,在模式串和主串匹配过程中,遇到不能匹配字符时,根据好后缀规则,移动过程如下:

    • 假设好后缀的长度是k。我们先拿好后缀,在suffix数组中查找其匹配的子串。
    • 如果suffix[k]不等于-1(-1表示不存在匹配的子串),那我们就将模式串往后移动j- suffix[k]+1位(j表示坏字符对应的模式串中的字符下标)。
      在这里插入图片描述
    • 如果suffix[k]等于-1,表示模式串中不存在另一个跟好后缀匹配的子串片段,可如下处理,注意这时prefix[k]中的k是小于suffix[k]中的k。
      在这里插入图片描述
    • 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串,我们就将整个模式串后移m位。
      在这里插入图片描述
      BM算法的完整版代码如下:
    func bm(mainStr []byte, modeStr []byte) int {
    	bc := make([]int, SIZE)
    	n := len(mainStr)
    	m := len(modeStr)
    	generateBC(modeStr, m, bc) //构建坏字符哈希
    	suffix := make([]int, m)
    	prefix := make([]bool, m)
    	generateGS(modeStr, suffix, prefix)
    	i := 0 //i表示主串与模式串对齐的第一个字符位置
    	for i <= n-m {
    		j := 0
    		for j = m - 1; j >= 0; j-- { //模式串从后往前匹配
    			if mainStr[i+j] != modeStr[j] {
    				break //坏字符对应模式串中的下标是j
    			}
    		}
    		if j < 0 {
    			return i //匹配成功,返回主串与模式串第一个匹配的字符的位置
    		}
    		x := j - bc[int(mainStr[i+j])] //坏字符规则算出来的移动位数
    		y := 0
    		if j < m-1 { //如果有好后缀(j = m-1时,表示没有好后缀)
    			y = moveByGS(j, m, suffix, prefix) //返回好后缀规则下,模式串移动的位数
    		}
    		i = i + mathutil.Max(x, y) //坏字符规则和好后缀规则,取移动位数更多的
    		//这里i一定大于0,因为若无好后缀,bc[int(mainStr[i+j])]为-1,那坏字符规则得到的移动位数一定大于0
    	}
    	return -1
    }
    
    //j表示坏字符对应的模式串中的字符下标,m表示模式串长度
    func moveByGS(j, m int, suffix []int, prefix []bool) int {
    	k := m - 1 - j       //好后缀长度
    	if suffix[k] != -1 { //模式串中存在和好后缀匹配的子串
    		return j - suffix[k] + 1
    	}
    	
    	//这个for循环就是遍历好后缀的后缀子串,看是否存在prefix[m-r]为true的情况
    	for r := j + 2; r <= m-1; r++ {
    		//j+2若为m,此时表示好后缀长度为1,此时移动m位即可
    		if prefix[m-r] == true { //m-r就是好后缀子串的长度
    			return r
    		}
    	}
    	//若好后缀的两个规则都不命中,则移动m位
    	return m
    }
    

    BM算法总结

    • BM算法核心思想是,利用模式串本身的特点,在模式串中某个字符与主串不能匹配的时候,将模式串往后多滑动几位,以此来减少不必要的字符比较,提高匹配的效率。
    • BM算法构建的规则有两类,坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存,为了节省内存,我们可以只用好后缀规则来实现BM算法。

    4. KMP算法

    • KMP算法的核心思想,跟上一节讲的BM算法非常相近。我们假设主串是a,模式串是b。
      在模式串和主串匹配过程中,把不能匹配的那个字符叫作坏字符,把已匹配的那段字符串叫作好前缀。
      在这里插入图片描述
    • 当遇到坏字符的时候,我们就要把模式串往后滑动,在滑动的过程中,只要模式串和好前缀有上下重合,前面几个字符的比较,就相当于拿好前缀的后缀子串,跟模式串的前缀子串在比较
      在这里插入图片描述
      KMP算法试图在模式串和主串匹配的过程中,当遇到坏字符后,对于已经比对过的好前缀,能否找到一种规律,将模式串一次性滑动很多位?
    • 我们只需要拿好前缀本身,在它的后缀子串中,查找最长的那个可以跟好前缀的前缀子串匹配的。
    • 假设最长的可匹配的那部分前缀子串是{v},长度是k。我们把模式串一次性往后滑动j-k位,相当于,每次遇到坏字符的时候,我们就把j更新为k,i不变,然后继续比较。
      在这里插入图片描述
    • 我们把好前缀的所有后缀子串中,最长的可匹配前缀子串的那个后缀子串,叫作最长可匹配后缀子串;对应的前缀子串,叫作最长可匹配前缀子串。
      在这里插入图片描述
    • 求好前缀的最长可匹配前缀子串和后缀子串时,只涉及模式串本身,因此可以预先处理。

    KMP算法提前构建一个数组,用来存储模式串中每个前缀(这些前缀都有可能是好前缀)的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为next数组。

    • 数组下标是每个前缀结尾字符下标,数组值是这个前缀的最长可匹配前缀子串的结尾字符下标
      在这里插入图片描述
    • 笨的方法,比如要计算下面这个模式串b的next[4],我们就把b[0, 4]的所有后缀子串,从长到短找出来,依次看看,是否能跟模式串的前缀子串匹配。很显然,这个方法也可以计算得到next数组,但是效率非常低。
      在这里插入图片描述
    如何高效计算next数组?
    • 假设next[i-1]=k,即b[0,k-1]是b[0,i-1]的最长可匹配前缀子串,如果b[0,k-1]的下一个字符b[k]与b[0,i-1]的下一个字符b[i]匹配,那子串b[0,k]就是b[0,i]的最长可匹配前缀子串,所以next[i]=k。
      在这里插入图片描述
    • 若b[0, k-1]的下一字符b[k]跟b[0, i-1]的下一个字符b[i]不相等呢?查看b[0,i-1]的次长可匹配前缀子串的下一个字符是否等于b[i],依次找下去
      在这里插入图片描述
      KMP算法代码完整版如下:
    func getNext(modeStr []byte) []int {
    	m := len(modeStr)
    	next := make([]int, m)
    	next[0] = -1 //表示好前缀长度为1,无后缀,next[0]为-1
    	k := -1      //初始为-1,表示最开始匹配时,无好前缀一说,还是要逐个字符匹配
    	for i := 1; i < m; i++ {
    		//如下这个for循环,即非简单+1的情况下,依次找next[k]的最长可匹配前缀子串的结尾字符下标
    		for k != -1 && modeStr[k+1] != modeStr[i] { //k!=-1表示当前已有好前缀
    			k = next[k]  //相当于求modeStr[:k]的最长可匹配前缀子串
    			//为什么是k=next[k],从上图看,y即是这里的k,已知next[i-1]=k,求next[i]
    			//因为modeStr[k+1]不等于modeStr[i],故只能看modeStr[:x](x取值为k-1到0)是否与modeStr[i-x:i]是否匹配
    			//常规操作是比较modeStr[k-1]是否等于modeStr[i],若不等,再看k-2,依次顺序比较
    			//假设modeStr[k-1]等于modeStr[i],那么还要看modeStr[:k-2]是否匹配modeStr[i-k+1:i-1],若不满足
    			//则不行,还得往下找,既然一定要满足这个条件,那么可以利用next[k]求出下一个
    			//最长可匹配前缀子串的位置,再比对下一个字符是否等于modeStr[i]
    		}
    		//如下情况,要么是k=-1,要么是modeStr[k+1] == modeStr[i]
    		if modeStr[k+1] == modeStr[i] {
    			k++
    		}
    		next[i] = k
    	}
    	return next
    }
    
    func kmp(mainStr, modeStr []byte) int {
    	n := len(mainStr)
    	m := len(modeStr)
    	next := getNext(modeStr)
    	j := 0
    	for i := 0; i < n; i++ { //i代表主串中与模式串首字符对齐的位置
    		for j > 0 && mainStr[i] != modeStr[j] {
    			j = next[j-1] + 1 //更新j为模式串下次开始匹配的字符位置
    			//next[j-1]表示当前好前缀是modeStr[:j-1]
    		}
    		if mainStr[i] == modeStr[j] { //j代表模式串中坏字符位置
    			j++
    		}
    		if j == m { //主串中找到匹配串
    			return i - m + 1
    		}
    	}
    	return -1
    }
    

    KMP算法总结

    • next数组计算的时间复杂度是O(m)
    • 匹配过程的时间复杂度是O(n)
    • KMP算法的时间复杂度是O(n+m)

    总结

    • BF算法是最简单、粗暴的字符串匹配算法,时间复杂度也比较高,是O(n*m),n、m表示主串和模式串的长度。不过,在实际的软件开发中,因为这种算法实现简单,对于处理小规模的字符串匹配很好用。
    • BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,有实验统计,它的性能是著名的KMP算法的3到4倍。

    leetcode字符串习题

    https://leetcode-cn.com/tag/string/

    展开全文
  • 大多数据结构课本中,涉及的内容即的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...

    大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。

    本文的逻辑顺序为
    1、最基本的朴素算法
    2、优化的KMP算法
    3、应算法需要定义的next值
    4、手动写出较短串的next值的方法
    5、最难理解的、足足有5行的代码的求next值的算法
    所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显不专业…

    一、问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    二、朴素算法

    最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例,一张动图模拟朴素算法:

    在这里插入图片描述
    这个算法简单,不多说,附上代码

    #include<stdio.h>
    int Index_1(char s[],int sLen,char p[],int pLen){//s为主串,sLen为主串元素个数,p为模式串,pLen为模式串的个数
        if(sLen<pLen)return 0;
        int i = 1,j = 1;
        while(i<=sLen && j<=pLen){
            if(s[i]==p[j]){i++;j++;}
            else{
                i = i-j+2;
                j = 1;
            }
        }
        if(j>pLen) return i-pLen;
        return 0;
    }
    void main(){
        char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
        char p[]={' ','a','b','a','a','b','c','a','c'};
        int sLen = sizeof(s)/sizeof(char)-1;
        int pLen = sizeof(p)/sizeof(char)-1;
        printf("%d",Index_1(s,sLen,p,pLen));
    }
    

    三、改进的算法——KMP算法

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?答案是肯定的。再看下面改进后的动图:
    在这里插入图片描述

    这个模拟过程即KMP算法,若没有看明白,继续往下看相应的解释,理解需要把P多移几位,然后回头再看一遍这个图就很明了了。

    相比朴素算法:
    朴素算法: 每次失配,S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1;T(n)=O(n*m)
    KMP算法: 每次失配,S串的索引i不动,P串的索引j定位到某个数。T(n)=O(n+m),时间效率明显提高

    而这“定位到某个数”,这个数就是接下来引入的next值。(实际上也就是P往后移多少位,换一种说法罢了:从上图中也可以看出,失配时固定i不变,令S[i]与P[某个数]对齐,实际上是P右移几位的另一种表达,只有为什么这么表达,当然是因为程序好写。)

    开——始——划——重——点!(图对逻辑关系比较好理解,但i和j的关系对后面求next的算法好理解!)

    • 比如,Pj处失配,绿色的是Pj,则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
      在这里插入图片描述

    • 假设P1…Pj-1中,P1…Pk-1与Pj-k+1…Pj-1是一一相等的,为了下面说的清楚,我们把这种关系叫做“首尾重合”
      在这里插入图片描述

    • 那么可以推出,P1…Pk-1与Si…Si+j-2
      在这里插入图片描述

    • 显然,接下来要做的就是把模式串右移了,移到哪里就不用多说了:
      在这里插入图片描述

    • 为了表示下一轮比较j定位的地方,我们将其定义为next[j],next[j]就是第j个元素前j-1个元素首尾重合部分个数加一,当然,为了能遍历完整,首尾重合部分的元素个数应取到最多,即next[j]应取尽量大的值,原因挺好理解的,可以想个例子模拟一下,会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即,对于字符串P,next[8]=4。如此,再看一下上面的动图是不是清楚了不少。

    • 最后,如果我们知道了一个字符串的next值,那么KMP算法也就很好懂了。相比朴素算法,当发生失配时,i不变,j=next[j]就好啦!接下来就是怎么确定next值了。

    四、手动写出一个串的next值

    我们规定任何一个串,next[1]=0。(不用next[0],与串的所有对应),仍是一张动图搞定问题:
    在这里插入图片描述
    这个扫一眼就能依次写出,会了这个方法,应付个期末考试没问题了。

    通过把next值“看”出来,我们再来分析next值,这就很容易得到超级有名的公式了,这个式子对后面的算法理解很重要!所以先要看懂这个式子,如果上面的内容通下来了,这个应该很容易看懂了:
    在这里插入图片描述

    五、求next的算法

    终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。

    int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
        next[1] = 0;
        int i = 1,j = 0;
        while(i<=cLen){
            if(j==0||ch[i]==ch[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    
    • 还是先由一般再推优化:
      直接求next[j+1](至于为什么是j+1,是为了和下面的对应)
      根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。
      不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序:
      if(P1…Pj-1 == P2…Pj) => next[j+1]=j
      else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
      else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2



      else if(P1P2 == Pj-1Pj) => next[j+1]=3
      else if(P1 == Pj-1) => next[j+1]=2
      else if(P1 != Pj-1) => next[j+1]=1

      每次前去尾1个,后掐头1个,直至得到next[j+1]

    • 再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组
      但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,
      ①next[j+1]的可能的最大值是多少(即从哪开始验证)
      ②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值)
      看一下的分析:

    1、next[j+1]的最大值为next[j]+1。
    因为:
    假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。
    如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+1
    2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
    这里不好解释,直接看下面的流程分析及图解

    开——始——划——重——点!
    从头走一遍流程
    ①求next[j+1],设值为m
    已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-1
    如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则
    已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
    ⑤第二第三步联合得到:
    P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
    ⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推

    上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解:
    1、要求next[k+1] 其中k+1=17
    在这里插入图片描述
    2、已知next[16]=8,则元素有以下关系:
    在这里插入图片描述
    3、如果P8=P16,则明显next[17]=8+1=9
    4、如果不相等,又若next[8]=4,则有以下关系

    在这里插入图片描述
    又加上2的条件知
    在这里插入图片描述
    主要是为了证明:
    在这里插入图片描述
    5、现在在判断,如果P16=P4则next[17]=4+1=5,否则,在继续递推
    6、若next[4]=2,则有以下关系
    在这里插入图片描述
    7、若P16=P2,则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0;遇到0时还没出结果,则递推结束,此时next[17]=1。最后,再返回看那5行算法,应该很容易明白了!

    展开全文
  • Python字符串匹配----6种方法的使用

    万次阅读 多人点赞 2018-09-29 16:34:45
    1. re.match 尝试从字符串的起始位置匹配一个模式,如果不是起始位置匹配成功的话,match()就返回none。 import re line="this hdr-biz 123 model server 456" pattern=r"123" matchObj = re.match( pattern, ...

    1. re.match 尝试从字符串的起始位置匹配一个模式,如果不是起始位置匹配成功的话,match()就返回none。

    import re
    
    line="this hdr-biz 123 model server 456"
    pattern=r"123"
    matchObj = re.match( pattern, line)
    
    


    2. re.search 扫描整个字符串并返回第一个成功的匹配。

    import re
    
    line="this hdr-biz model server"
    pattern=r"hdr-biz"
    m = re.search(pattern, line)


    3. Python 的re模块提供了re.sub用于替换字符串中的匹配项。

    import re
    
    line="this hdr-biz model args= server"
    patt=r'args='
    name = re.sub(patt, "", line)



    4. compile 函数用于编译正则表达式,生成一个正则表达式( Pattern )对象,供 match() 和 search() 这两个函数使用。

    import re
    
    pattern = re.compile(r'\d+') 

     

    5. re.findall 在字符串中找到正则表达式所匹配的所有子串,并返回一个列表,如果没有找到匹配的,则返回空列表。

    import re
    
    line="this hdr-biz model args= server"
    patt=r'server'
    pattern = re.compile(patt)
    result = pattern.findall(line)


    6. re.finditer 和 findall 类似,在字符串中找到正则表达式所匹配的所有子串,并把它们作为一个迭代器返回。

    import re
    
    it = re.finditer(r"\d+","12a32bc43jf3")
    for match in it:
      print (match.group() )

     

    展开全文
  • 1.判断字符串是否满足条件: (1)以aaa 、bbb或 ccc 开头 (2)中间为0个到10为数字 (3)“#” 结束 public static void main(String[] args) { String regex = "(aaa|bbb|ccc)\\d{0,10}#$"; String...

    1.判断字符串是否满足条件:

         (1)以aaa 、bbb或 ccc 开头

         (2)中间为0个到10为数字

         (3)“#” 结束

     

     public static void main(String[] args) {
            String regex = "(aaa|bbb|ccc)\\d{0,10}#$";
    
            String str = "aaa1";
            String str1 = "aaa#";
            String str2 = "aaabbb#";
    
            String str3 = "aaa1#";
            String str4 = "bbb0123#";
            String str5 = "aaabbb12#";
    
            System.out.println(str+":  "+str.matches(regex));
            System.out.println(str1+":  "+str1.matches(regex));
            System.out.println(str2+":  "+str2.matches(regex));
            System.out.println(str3+":  "+str3.matches(regex));
            System.out.println(str4+":  "+str4.matches(regex));
            System.out.println(str5+":  "+str5.matches(regex));
    
        }

    结果:

     

     在 "(aaa|bbb|ccc)\\d{0,10}#$"字符串中,

         "\d"表示数字 ,由于"\"是特殊字符,所以需要转义,即通过“\\d”表示数字;字符串中“\\d”也可用“[0-9]”替换。

        “\\d{0,10}” 表示有0个到10个数字;

          “$" 表示字符串结束。

     

     

    更多特殊字符、非打印字符等可参考            菜鸟教程:菜鸟教程 _正则表达式 _语法

     

    2、从字符串中提取子字符串

           (1)判定一个字符串是否是手机号,若是则输出标准化的手机号(11位),否则输出提示。

           (2)正确的手机号可能包含前缀:+86或 +86-   , 11位手机号已有可能被“-”划分成3部分。即3位+4位+4位。如下为正确的手机号:+8614763665566      +86-14763665566    +86147-6366-5566      +86-147-6366-5566

     

    public static void main(String[] args) {
            String regex = "(\\+86|\\+86-)?(147-(\\d{4})-(\\d{4})|147\\d{8})$";  //正确的手机号满足该表达式
    
            String phone= "+86147-6366-5566";
            Pattern pattern = Pattern.compile(regex);
            Matcher matcher = pattern.matcher(phone);
            if (matcher.matches()) {
                System.out.println("matcher.group(0) :"+matcher.group(0));//原始字符串
                System.out.println("matcher.group(1) :"+matcher.group(1));//第一个括号
                System.out.println("matcher.group(2) :"+matcher.group(2));//第二个括号(嵌套时,外层括号优先级高)
    
                System.out.println("标准的手机号为: " +matcher.group(2).replace("-",""));
            }
            else{
                System.out.println("error!!!");
            }
    
        }
    
    
    
    
    
    输出结果为:
    
    matcher.group(0) :+86-147-6645-9636
    matcher.group(1) :+86-
    matcher.group(2) :147-6645-9636
    标准的手机号为: 14766459636
    
    Process finished with exit code 0

    ①每个括号中的式子都是一个独立的表达式;

    ②如果字符串变量phone符合约定的格式,则第二个括号里的值就是去掉前缀的手机号;因此将第二个括号里可能存在的“-”字符去除,就得到标准的手机号。

     

     

    展开全文
  • 字符串匹配算法之KMP

    千次阅读 多人点赞 2020-07-22 22:46:55
    目录需求基础知识逻辑解析源码实现 需求 先简单描述溪源曾经遇到的需求: 需求一:项目结果文件中实验结论可能会存在未知类型、转换错误、空...方案三:依次匹配字符串中字符(暴力匹配); 以上两种方案都能解决;然
  • 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。 示例 1: 输入: haystack = &amp;amp;quot;hello&amp;amp;...
  • iOS之字符串截取、iOS 字符串替换、iOS字符串分隔、iOS之字符串匹配、截取字符串、匹配字符串、分隔字符串 1.iOS 字符串截取 //1.ios截取字符串 NSString *string =@"123456d890"; NSString *str1 = ...
  • 字符串匹配这样一个功能,我想对于任何一个开发工程师来说,应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数,比如Java中的 indexOf(),Python 中的find()函数等,它们底层就是依赖接下来要讲的...
  • Java实现字符串匹配

    万次阅读 多人点赞 2019-07-20 21:29:47
    给定一个n个字符组成的(称为文本),一个m(m <= n)的(称为模式),从文本中寻找匹配模式的子串。 2 解决方案 2.1 蛮力法 package com.liuzhen.chapterThree; public class BruteForceStringMatch { //...
  • Tcl的字符串操作:字符串匹配

    千次阅读 2019-04-07 16:15:04
    所谓字符串匹配是指检测待测字符串(也可称为目标字符串)是否与给定的模式相匹配。这里的模式其实也是字符串;Tcl提供了两种字符串匹配方法:一种为通配符模式,一种为正则表达式。这里先介绍较为简单易用的通配符...
  • 做查询遇到一个坑,想用字符串去判断是否等于一个数字字符串"1",没报错但匹配不上,写法如下 and task_id like CONCAT(CONCAT('TASK', #{taskIdType}), '%') 正确写法如下 and task_id like CONCAT(CONCAT('TASK...
  • 字符串匹配查询

    万次阅读 2018-05-18 11:45:50
    mysql中数据有两个运算符来提供字符字符串查询匹配的,分别是like和regexp,下面来看一下。mysql&gt; select * from tmp; +------+----------+ | id | name | +------+----------+ | 2 | lisi | | 1 | zhangsan |...
  • Java实现 蓝桥杯 算法提高 字符串匹配

    千次阅读 多人点赞 2020-04-23 18:25:05
    试题 算法提高 字符串匹配 问题描述  给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,...
  • 字符串匹配算法(BM)

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

    万次阅读 多人点赞 2020-04-04 21:42:48
    686. 重复叠加字符串匹配 给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。 举个例子,A = “abcd”,B = “cdabcdab”。 答案为 3, 因为 A ...
  • 字符串匹配算法-KMP

    千次阅读 2020-03-08 14:30:17
    文章目录字符串匹配问题KMP算法简介前缀/后缀/部分匹配表甲的疑问1:k = next[k-1]是什么鬼?结论得到部分匹配表后匹配过程算法总结 字符串匹配问题 引用知乎用户灵茶山艾府的举例,假设我们有两个角色,甲和乙 甲:...
  • 用java实现字符串匹配问题

    千次阅读 2020-06-29 12:30:47
    考题:判断字符串 a 是否包含字符串 b,这里称 a 为文本串,b 为模式串。 代码如下: import java.util.Scanner; public class demo { /** * 判断是否匹配 * * @param target 目标文本串 * @param mode 模式...
  • 小白专属的《算法与数据结构》,夯实基础,直击面试!
  • 字符串匹配算法

    千次阅读 2018-11-05 17:58:47
    网络信息中充满大量的字符串,对信息的搜寻至关重要,因此子字符串查找(即字符串匹配)是使用频率非常高的操作:给定一段长度为N的文本和长度为M的模式字符串(N≥M),在文本中找到一个和模式串相匹配的子串。...
  • 字符串算法之KMP(字符串匹配

    千次阅读 多人点赞 2018-06-17 16:15:34
      给定一个主(以 S 代替)和模式(以 P 代替),要求找出 P 在 S 中出现的位置,此即的模式匹配问题。   Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳...
  • jq字符串匹配

    千次阅读 2018-08-31 11:36:59
    $(function(){  var str="sunny,woo";  var sear=new RegExp('sun');  if(sear.test(str)){  alert('Yes');  }  var tag=',';  if(str.indexOf...
  • Python 字符串匹配 match

    千次阅读 2019-04-23 19:25:25
    Python 字符串匹配 match
  • 字符串匹配算法综述

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

    千次阅读 2020-04-22 16:00:37
     给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符;当选项关闭时,表示同一个字母的大写和小写看作相同...
  • 942. 增减字符串匹配

    千次阅读 2019-06-30 01:12:59
    给定只含"I"(增大)或 "D"(减小)的字符串S,令N = S.length。 返回[0, 1, ..., N]的任意排列A使得对于所有i = 0,..., N-1,都有: 如果S[i] == "I",那么A[i] < A[i+1] 如果S[i] == "D",那么A[i] > A[i...

空空如也

1 2 3 4 5 ... 20
收藏数 81,571
精华内容 32,628
关键字:

字符串匹配