精华内容
下载资源
问答
  • 2021-11-01 13:18:44

    28 实现 strStr()

    判断一个字符串是不是另一个字符串的子字符串,并返回其位置。

    输入一个母字符串和一个子字符串,输出一个整数,表示子字符串在母字符串的位置,若不存在则返回-1。

    输入:haystack = “hello”, needle = “ll”
    输出:2

    解析:

    ​ 解决本题一种简单的思路是暴力匹配:首先将子串和母串左端对齐;然后逐个比较对应的字符,如果发现不匹配则将子串开始匹配位置相对于母串后移动一位,同时将比较指针回溯到子串头部;重复匹配过程,直到找到对应子串,不存在则返回 -1。

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int m = haystack.length(), n = needle.length();
            for(int i=0;i+n<=m;++i){
                bool flag = true;
                for(int j=0;j<n;++j){
                    if(haystack[j+i]!=needle[j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    return i;
                }
            }
            return -1;
        }
    };
    

    ​ 上述方法的比较指针不断回溯的过程会增加时间复杂度,一种优化方法就是 KMP 算法。KMP 算法的核心思想就是通过寻找已匹配部分子串中的相同前后缀,在遇到字符不匹配的情况时,直接将子串从前缀部分移动到后缀,避免比较指针直接回溯到子串头部

    ​ 如下例所示,母串和子串在第 8 个字符出现不匹配,下一步匹配操作:如果使用暴力匹配则是将匹配指针回溯到子串头部并往后移动一位再次寻找与母串左端对齐;如果使用KMP算法,可以看到子串已经匹配的相同最长前后缀为ABC,直接将整个子串从前缀位置移动到后缀,一次性移动四位,避免比较指针从头再开始匹配。

    原串暴力匹配KMP 算法
    ABCFABCFABCAABCFABCFABCAABCFABCFABCA
    ABCFABCA0ABCFABCA0000ABCFABCA

    ​ KMP 算法的关键是在子串中找到最长前后缀,这里可以采用动态规划的思想

    ​ 设置状态:构建一个数组 next[i]表示子串中对应位置 i 之前的部分串中最长前后缀的长度。

    ​ 状态转移方程:对于位置 i,如果下一位前后缀相同,更新相同最大前后缀的长度;如果下一位不同,则将向前回溯。

    ​ 初始情况:如果仅有一个字符不存在前后缀,next[0]=-1 。前缀指针从 -1 位置开始,后缀指针从 1 位置开始遍历子串。

    // 计算前缀表 next
    void getNext(string needle, vector<int>& next){
        int head = -1;
        next[0] = -1;
        for(int tail = 1; tail<needle.length();++tail){
            // 如果下一位不同,往前回溯,回溯到没有前缀为止(head=-1)
            while(head>-1 && needle[head+1]!=needle[tail]){
                head = next[head];
            }
            // 如果下一位相同,更新相同的最大前缀和最大后缀长,同时移动前缀指针
            if(needle[head+1]==needle[tail]){
                ++head;
            }
            next[head] = head;
        }
    }
    

    ​ 一个上述计算ABCFABCA前缀表的例子:

    next 索引部分子串最长前缀最后一个元素的位置 next[i]
    0A-1
    1AB-1
    2ABC-1
    3ABCF-1
    4ABCFA0
    5ABCFAB1
    6ABCFABC2
    7ABCFABCA2
    class Solution {
    public:
    	// 计算前缀表 next
        void getNext(string needle, vector<int>& next){
            int head = -1;
            next[0] = -1;
            for(int tail=1;tail<needle.length();++tail){
                // 如果下一位不同,往前回溯,回溯到没有前缀为止(head=-1)
                while(head>-1 && needle[head+1]!=needle[tail]){
                    head = next[head];
                }
                if(needle[head+1]==needle[tail]){
                    ++head;
                }
                next[tail] = head;
            }
        }
    
        int strStr(string haystack, string needle) {
            int cur = -1;
            int m = haystack.size(), n = needle.size();
            // 子串为空返回 0 
            if(n==0) return 0;
            // 获取前缀表
            vector<int> next(n,-1);
            getNext(needle,next);
            for(int i=0;i<m;++i){
                while(cur>-1 && haystack[i]!=needle[cur+1]){
                    cur = next[cur];
                }
                if(haystack[i]==needle[cur+1]){
                    ++cur;
                }
                // 说明=cur移动到needle的最末端,此时i也指向母串中匹配子串的最后一个位置,返回此时匹配子串最左端的位置
                if(cur == n-1){
                    return i - cur;
                }
            }
            return -1;
        }
    };
    

    参考资料

    LeetCode 101:和你一起轻松刷题(C++) 第 12 章 令人头大的字符串

    更多相关内容
  • 字符串匹配

    千次阅读 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/

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

    万次阅读 多人点赞 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;
    }
    展开全文
  • 字符串匹配算法知多少?

    千次阅读 多人点赞 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算法

    展开全文
  • 字符串匹配算法(BM)

    万次阅读 多人点赞 2019-06-22 04:12:15
    文章目录1. BM(Boyer-Moore)算法 1. BM(Boyer-Moore)算法 思想:有模式中不存在的字符,那么肯定不匹配,往后多移动几位,提高效率 BM原理:坏字符规则,好后缀规则 ...
  • 最近在写一个程序,需要用到字符串匹配,并且返回匹配的字符串,C语言库函数中的strtstr无法满足我的要求,只能自己写了。 代码如下 //string match function char *matchString(const char* buf, const char* sub) ...
  • 字符串匹配原理及实现(C++版)

    万次阅读 多人点赞 2018-12-05 16:09:01
    字符串匹配原理及实现(C++版)1. 字符串匹配概念2. BF3. KMP4. BM5. 性能总结 1. 字符串匹配概念 2. BF 3. KMP 4. BM 5. 性能总结
  • Java 字符串匹配的三种方法

    千次阅读 2021-04-11 20:50:44
    如图,都是为了替换字符串s中的"("符号,但三种匹配方法,有三种不同的效果及写法。 二、解释 1.replace()方法 replace()方法没有用到正则表达式,但会匹配所有的参数并进行替换 2.replaceAll()方法 replaceAll()...
  • 字符串匹配算法之KMP

    千次阅读 多人点赞 2020-07-22 22:46:55
    目录需求基础知识逻辑解析源码实现 需求 先简单描述溪源曾经遇到的需求: 需求一:项目结果文件中实验结论可能会存在未知类型、转换错误、空...方案三:依次匹配字符串中字符(暴力匹配); 以上两种方案都能解决;然
  • 《C语言》字符串匹配(BF算法+KMP算法)

    千次阅读 多人点赞 2020-05-02 16:07:17
    字符串匹配 【问题描述】 对于字符串S和T,若T是S子串,返回T在S中的位置(T的首字符在S中对应的下标),否则返回-1. 【问题求解】 采用直接穷举法求解,称为BF算法。该算法从S的每一个字符开始查找,看T是否会出现...
  • Java正则表达式字符串匹配示例

    千次阅读 2021-03-05 23:41:12
    使用正则表达式对字符串进行全部替换,表达式为: String reg = "(?s)'.*'"; 这里我们改写一下代码 Pattern p =Pattern.compile("(\\[标题BEGIN\\](.*)\\[标题END\\])",Pattern.DOTALL); 回车换行也能匹配了。 ...
  • 字符串匹配算法

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

    千次阅读 2021-01-08 14:19:18
    因此,字符串匹配算法的时间复杂度就是 n 和 m 的函数。 假设要从主串 s = “goodgoogle” 中找到 t = “google” 子串。根据我们的思考逻辑,则有: 首先,我们从主串 s 第 1 位开始,判断 s 的第 1 个字符是否...
  • 字符串匹配(JS实现)

    千次阅读 2019-08-28 19:15:29
    判断第一个字符串是否包含第二个字符串 function change(str1, str2) { if (str1 === str2) { return true } let arr1 = [...str1] let arr2 = [...str2] if (arr2.length > arr1.length) { ...
  • LeetCode简单题之数组中的字符串匹配

    千次阅读 2022-03-16 17:27:49
    给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么...
  • 字符串匹配(多模式匹配篇)

    千次阅读 2018-05-12 22:39:22
    字符串匹配(多模式匹配篇)摘要:问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve多模式串匹配问题呢?Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的...
  • 字符串算法之KMP(字符串匹配

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

    千次阅读 2021-04-25 11:17:02
    如下所示,这是一个简单的字符串匹配: int strmatching(const string &T,const string &P) { int p=0; int t=0; int plen=P.length(); int tlen=T.length(); if(tlen<plen) return -1; else {...
  • SQL字符串匹配和运算

    千次阅读 2019-05-28 09:58:58
    匹配 百分号(%):匹配任意子串 select dept_name from department where building like ‘%Watson’; (或前缀匹配Watson%) 下划线(_):匹配任意单个字符 ...假如匹配字符串中包含特殊字符(%...
  • 字符串匹配算法(多模式串)

    千次阅读 2019-02-23 22:35:40
    是一种专门用来处理字符串匹配的数据结构,用来解决在一组字符串中快速查找某个字符串的问题。 谷歌,百度这种搜索引擎,输入框的关键词提示功能,底层原理就是使用了这种数据结构 Tire树是一种有序树,用于保存关联...
  • C#实现字符串匹配算法

    千次阅读 2018-02-07 00:24:55
    刚学习完字符串匹配的几种算法:BF算法、MP算法:KMP算法,BM算法和BMH算法。参考的书籍是算法之美,原书的代码都是用C++写的。我不懂C++,只学过C#,这里就用C#做个总结(自己是个菜鸟,表达错误的地方,希望大家...
  • 实现KMP字符串匹配

    千次阅读 2020-04-16 19:55:40
    KMP 字符串匹配算法可以实现高效的匹配。 假设长字符串为t,短字符串为p。为了进行 KMP 匹配,首先需要计算字符串p的next数组,后面实现了计算该数组的函数void KmpGenNext(char* p, int* next)。对于 “abcabcab” ...
  • 编写函数,计算字符串匹配的准确率 #编写函数,计算字符串匹配的准确率 def Rate(origin,userInput): if not (isinstance(origin,str) and isinstance(userInput,str)): print('The two parameters must be ...
  • C语言实现字符串匹配KMP算法

    千次阅读 2016-12-05 16:12:14
    相信很多人(包括自己)初识KMP算法的时候始终是丈二和尚...字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KM
  • SQL中的字符串匹配

    千次阅读 2020-02-29 22:45:23
    找出满足给定匹配条件的字符串。 列名 [not] like "字符串" 2. 匹配原则 %:匹配零个或多个字符 _:匹配任意单个字符 \:转义字符,可以去掉特殊字符的特点含义,使其作为普通字符看待,可以\%去匹配%,\_ 去匹配 _...
  • 字符串匹配之暴力匹配

    千次阅读 2018-04-05 16:48:29
    字符串匹配之暴力匹配 字符串匹配就是在一个字符串集里面找到某个模式串出现的所有位置。 例如,找出模式P=abaaP=abaaP=abaa在文本T=abcabaabcabacT=abcabaabcabacT=abcabaabcabac中的位置,用mmm和nnn分别表示PPP...
  • 字符串匹配--朴素算法

    千次阅读 2018-05-02 18:08:15
    假设有两个字符串M="abcdefabcdx";T="abcdx";想要找到T串在M串中的位置,要怎么找呢?通过画图来看比较过程:也就是说,从主串M的第一个字符开始分别与子串从开头进行比较,当发现不匹配时,主...
  • 字符串匹配算法(单模式串)

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 ...字符串的匹配算法有:单模式串匹配算法(BF算法,RK算法,BM算法,KMP算法), 多模式串匹配算法(Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • Python 字符串匹配、搜索及替换

    千次阅读 2019-12-31 23:11:45
    文章目录字符串匹配、搜索及替换字符串开头或结尾匹配str.startswith() 和 str.endswith()用 Shell 通配符匹配字符串fnmatch() 和 fnmatchcase()字符串匹配和搜索 字符串匹配、搜索及替换 字符串开头或结尾匹配 ...
  • 利用有限自动机进行字符串匹配

    千次阅读 2019-02-08 18:40:52
    Q:Finite Automaton?,我根本就没有听说过这种数据结构,毫不关心无压力.jpg A:这个还是有点儿用处的,...朴素字符串匹配算法就是通过一个循环找到所有的有效偏移,对于n-m+1个可能的s,我们需要检测P[1...m]==T[...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,074,400
精华内容 429,760
关键字:

字符串匹配