精华内容
下载资源
问答
  • 第76篇 C++实现字符串匹配(一)BF算法
    2021-11-17 22:04:09

    第76篇 C++实现字符串匹配(一)BF算法

    1.BF算法简单描述

    Stringmatching,字符串匹配,可以看成在数组中查找值,区别在于是在串中找另一个串,那么就得一一匹配串里面的每一个字符是否都相等,最简单的方法就是一个一个去匹配。
    从主串第一个字符开始,子串也从第一个开始,两个串都往后依次匹配,当子串某个字符匹配不成功,就将主串回溯到第二位,子串回到第一位,如此反复匹配,直到匹配成功或者到达主串剩余长度小于子串长度为止,成功就返回此次匹配成功的第一次成功位置(子串在主串中的起始位置),这就是BF算法—暴力检索。
    且看以下两个字符串。

    012345678910
    Sabcabcmnabc
    Tabcm

    (1)第一次匹配,从s的0开始,s[0]和t[0]相等,第一位匹配成功,到下标为3时,s[3]和t[3]不相等,s回到1,t回到0;
    (2)第二次匹配s[1]就不等于t[0],所以s前进到2,t依然是0;
    (3)第三次匹配s[2]就不等于t[0],所以s前进到3,t依然是0;
    (4)第四次匹配s[3]就等于t[0],s和t同时往后,s[4]等于t[1],s[5]等于t[2],s[6]等于t[3],匹配成功,返回的位置是3;

    有一点注意的是,直到匹配成功或者到达主串剩余长度小于子串长度为止,因为超过的长度已经没有匹配的意义了。比如以上字符串,主串最多移动到7位置就行了,到8之后没有意义,所以可以减少一些时间。主串移动的最多次数是s.length – t.length;如果i是s的下标,那么i的循环条件是s.length – t.length + 1;

    2.代码实现

    BF算法有很多写法,以下是我简单些的代码。

    #include <iostream>
    using namespace std;
    #include <string>
    
    //Brute Force BF算法   暴力检索
    int bruteForce(string mainString, string target);
    void bruteForceTest();
    
    int main() {
    	bruteForceTest();
    	return 0;
    }
    
    //Brute Force BF算法   暴力检索
    int bruteForce(string mainString, string target) {
    	int mlen = mainString.size();
    	int tlen = target.size();
    	//只需要移动mlen - tlen次就行了
    	//剩下的长度比target的长度小了,不可能匹配成功
    	int n = mlen - tlen + 1;
    	for(int i = 0;i < n;i++) {
    		int j = 0;
    		for(;j < tlen;j++) {
    			if(mainString[i + j] != target[j]) {
    				break;
    			}
    		}
    		if(j == tlen) {
    			return i;
    		}
    	}
    	
    	return -1;
    }
    
    void bruteForceTest() {
    	string mainString;
    	string target;
    	int contin = 1;
    	do {
    		system("cls");
    		cout << "当前检测的是BF(BruteForce)算法\n" << endl;
    		cout << "请输入mainString:";
    		cin >> mainString;
    		cout << "请输入target:";
    		cin >> target;
    		
    		int result =  bruteForce(mainString, target);
    		if(result != -1) {
    			cout << target << "的起始位置在" << mainString << "的" << result << "处" << endl;
    		}
    		else {
    			cout << target << "不在" << mainString << "中" << endl;
    		}
    		
    		cout << "继续检测输入1,否则输入0:";
    		cin >> contin;
    	} while (contin == 1);
    	cout << "欢迎再次检测!" << endl;
    }
    

    3.另外说明

    看了很多网上视频,我学到了一点就是,给每个函数写一个单独测试函数,这样你想测试这个函数的时候,你就单独拿函数对应的测试函数过来就行了,而不是在主函数了增删改的去做测试。
    如果是面向对象语言,那我们还可以把这个写得简单些。因为string是对char*的封装,所以我们直接用内置函数来操作就行。
    如:

    //Brute Force BF算法   暴力检索
    int bruteForce(string mainString, string target) {
    	int mlen = mainString.size();
    	int tlen = target.size();
    	//只需要移动mlen - tlen次就行了
    	//剩下的长度比target的长度小了,不可能匹配成功
    	int n = mlen - tlen + 1;
    	for(int i = 0;i < n;i++) {
    		int j = 0;
    		string s = mainString.subStr(i , tlen);
    		if(s == target) {
    			return i;
    		}
    	}
    	return -1;
    }
    

    当然了,其实匹配函数也帮我们写好了,自己写一写只是锻炼自己的思维,因为明白怎么做也是一个好处,学习算法可以锻炼思维,发散思维,当你想到一个方法实现的时候,也许就会想到更多的方法解决了。
    记住写出一个功能函数的时候,记得给它写一个测试函数,这样以后你还想测试的时候就会很方便,直接在主函数调用就行了,我记得刚开始的时候,我想看哪个函数功能能不能实现,都是在主函数删掉其他函数的测试内容,或者注释掉其他内容,显得主函数又长又臭。。。。。。。
    还有避免函数的多次调用,比如字符串的长度,如果把循环条件改成

    for(int i = 0;i < mainString.size() - target.size();i++) {
    }
    

    那就会涉及函数多次调用,循环条件多次计算,会消耗空间和时间,函数调用会进栈,用完才出栈,这样写就会有不停的出栈和进栈。
    当然了,如果你的字符串或者数组在使用的过程中长度会发生变化,那就这样写了。

    4.结语

    代码尽量简洁,避免重复不必要的操作。

    更多相关内容
  • 模式匹配BF算法C/C++代码实现

    千次阅读 2020-06-05 11:25:13
    串: 串是一种内容受限的线性表。 与线性表基本操作不同的是...( 为了方便说明问题,算法描述当中所用到的顺序存储的字符串都是从下标为1的数组分量开始存储的, 下标为0的分量闲置不用) #include<stdio.h> #

    串:

    串是一种内容受限的线性表。
    与线性表基本操作不同的是,串是以“串的整体”作为操作对象的。

    考虑到存储效率和算法的方便性, 串多采用顺序存储结构。

    BF算法:

    算法思想简明,从始位置开始逐一匹配,匹配成功继续下一个,若失败则回溯:
    主串的指针i总是回溯到 i-j+2 位置,
    模式串的指针总是恢复到首字符位置 j= 1
    在这里插入图片描述

    代码如下:

    ( 为了方便说明问题,算法描述当中所用到的顺序存储的字符串都是从下标为1的数组分量开始存储的, 下标为0的分量闲置不用)

    #include<stdio.h>
    
    #define MAXLEN 255
    
    //串的顺序存储
    typedef struct
    {
    	char ch[MAXLEN + 1];	//0号不用,从1开始
    	int length;				//串的当前长度
    }SString;
    
    //BF算法
    //返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在, 则返回值为0 
    int Index_BF(SString S, SString T, int pos)
    {
    	int i = pos;	//主串起始位置
    	int j = 1;		//模式串起始位置
    
    	while (i<=S.length && j<=T.length)
    	{
    		if (S.ch[i] == T.ch[j])	//若相等 主串子串都往后移一位
    		{
    			++i;
    			++j;
    		}
    		else					//不相等 主串回溯到i - j + 2,子串从头再来
    		{
    			i = i - j + 2;
    			j = 1;
    		}
    	}
    	if (j > T.length) return i - T.length;	//匹配成功
    	else return 0;							//匹配失败
    }
    
    
    int main()
    {
    	SString S, T;
    	S.ch[0]='#';	//0号不用,从1开始
    	T.ch[0]='#';
    
    	//输入
    	printf("请输入主串S的长度:");
    	scanf("%d", &S.length);
    	printf("请输入主串S:");
    	scanf("%s", (S.ch)+1);	//0号不用,从1开始
    
    	printf("请输入子串T的长度:");
    	scanf("%d", &T.length);
    	printf("请输入子串T:");
    	scanf("%s", (T.ch) + 1);	//0号不用,从1开始
    
    	//输出
    	printf("\nS:");
    	for (int i = 1; i <= S.length;i++)
    	{
    		printf("%c", S.ch[i]);
    	}	
    	printf("\nT:");
    	for (int i = 1; i <= T.length; i++)
    	{
    		printf("%c", T.ch[i]);
    		
    	}
    	int index=Index_BF(S, T, 1);
    	printf("\n你要查找的位置为:%d\n",index);
    }
    

    运行结果:

    在这里插入图片描述

    展开全文
  • 字符串模式匹配 模式串(或子串)在主串中的定位操作通常称为串的模式匹配,它是各种串处 理系统中最重要的运算之一。 BF算法 布鲁特-福斯算法 从主串的第一个字符起与模式串的第一个字符比较,若相等,则继续逐个字 ...

    字符串模式匹配
    模式串(或子串)在主串中的定位操作通常称为串的模式匹配,它是各种串处
    理系统中最重要的运算之一。

    BF算法

    布鲁特-福斯算法
    从主串的第一个字符起与模式串的第一个字符比较,若相等,则继续逐个字
    符进行后续比较,否则从主串的第二个字符起与模式串的第一个字符重新开始比较,直至模式串中每个字符依次与主串中的一个连续的字符序列相等时为止,此时称为匹配成功;如果在主串中不存在与模式串相同的子串,则匹配失败。

    图解过程

    给定主串“ABCDABCDABBABCDABCDABDD”,子串“ABCDABD”
    1、第一趟比较,先比较 A,然后是 BCDAB。
    在这里插入图片描述
    在比较最后一个字符 D 时,不匹配。
    在这里插入图片描述
    2、第二趟比较,主串回退到比前一趟加 1 的位置。子串从 0 开始。第一个就不匹配。结束本趟。
    在这里插入图片描述
    3、第三趟比较,主串回退到比前一趟加 1 的位置,子串从 0 开始。第一个还是不匹配。同样结束本趟。
    在这里插入图片描述
    ……
    i、第 i 趟比较,找到可以匹配的子串
    在这里插入图片描述

    /****************************************************************
     * 函数名称:searchFS
     * 功能描述:布鲁特-福斯模式匹配
     * 参数说明:src, 主串
     *			sub, 模式串
     * 返 回 值:-1,表示不成功,非0的值表示模式串sub在主串src的位置
    *****************************************************************/
    int searchFS(const char *src, const char*sub)
    {
    	int i, j;
    	i = 0;
    	j = 0;
    	int strLen = strlen1(src);
    	int tLen = strlen1(sub);
    	while (i<strLen && j<tLen)
    	{
    		if (src[i] == sub[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			//主串回退
    			i = i - j + 1;
    			//子串
    			j = 0;
    		}
    	}
    	if (j >= tLen)
    	{
    		return (i - tLen);
    	}
    	return -1;
    }
    
    int searchFS(const char *src, const char*sub, int pos)
    {
    	int i, j;
    	i = pos;
    	j = 0;
    	int strLen = strlen1(src);
    	int tLen = strlen1(sub);
    	while (i<strLen && j<tLen)
    	{
    		if (src[i] == sub[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			//主串回退
    			i = i - j + 1;
    			//子串
    			j = 0;
    		}
    	}
    	if (j >= tLen)
    	{
    		return (i - tLen);
    	}
    	return -1;
    }
    
    
    /****************************************************************
     * 函数名称:searchFSAll
     * 功能描述:查找模式串在主串中所有的出现的位置
     * 参数说明:locArr, 位置的数组
     *			src, 主串
     *			sub, 模式串
     * 返 回 值:0,表示没有匹配的,非值,表示有匹配的个数
    *****************************************************************/
    int searchFSAll(int locArr[],const char *src, const char *sub)
    {
    	//调用
    	int i = 0;
    	int srcLen = strlen1(src);
    	int subLen = strlen1(sub);
    	//int res = searchFS(src, sub, 0);
    	//if (res != -1)
    	//{//找到了 , res是当前的一个位置 (排除 ABABACDABAC   ABA)
    	//	//记录res
    	//	locArr[i] = res;
    	//	i++;
    	//	res += subLen;
    	//	res = searchFS(src, sub, res);
    	//}
    
    	int res = 0;
    	int bj = 0;
    	while ((res = searchFS(src, sub, res)) != -1)
    	{
    		++bj;//表示找到一个,加1
    		locArr[i] = res;
    		i++;
    		res += subLen;
    	}
    
    	return bj;
    }
    

    代码实现

    #include<stdio.h>
    #include<string.h> 
    
    int BF(const char*s,const char*p)
    {
    	int lens=strlen(s);
    	int lenp=strlen(p);
    	
    	if(s==NULL||p==NULL||lenp>lens) return -1;
    	
    	int i=0;
    	int j=0;
    	while(i<lens&&j<lenp)
    	{
    		if(s[i]==p[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(j==lenp)
    	{
    		return i-j;
    	}
    	return -1;
    	
    }
    
    int main()
    {
    	const char *s="ababcabcdabcde";
    	const char *p="abcd";
    	
    	printf("%d\n",BF(s,p));
    	return 0;
    }
    

    在这里插入图片描述

    增加pos位置的方法

    #include<stdio.h>
    #include<string.h> 
    
    int BF(const char*s,const char*p,int pos)
    {
    	int lens=strlen(s);
    	int lenp=strlen(p);
    	
    	if(s==NULL||p==NULL||lenp>lens) return -1;
    	
    	int i=pos;
    	int j=0;
    	while(i<lens&&j<lenp)
    	{
    		if(s[i]==p[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(j==lenp)
    	{
    		return i-j;
    	}
    	return -1;
    	
    }
    
    int main()
    {
    	const char *s="ababcabcdabcde";
    	const char *p="abcd";
    	
    	printf("%d\n",BF(s,p,6));
    	return 0;
    }
    
    

    性能分析

    在这里插入图片描述

    展开全文
  • 目录BFRKBM坏字符规则好后缀规则KMPnext BF Brute Force,暴力破解,时间复杂度最大为O(mn) bool patternMatching(string pattern, string value) { int m = pattern.size(); int n = value.size(); for(int ...

    BF

    Brute Force,暴力破解,时间复杂度最大为O(mn)

    bool patternMatching(string pattern, string value) {
            int m = pattern.size();
            int n = value.size();
           
            for(int i = 0; i <= (n-m); i++){
                int begin = i;
                bool flag = true;
                for(int j = 0; j < m; j++){
                    if(pattern[j]!= value[begin+j]){
                        flag = false;
                        break;
                    }    
                }
                if(flag) return true;
            }
            return false;
        }
    
    

    RK

    上文的BF算法,最坏的情况可能可能是这样

    pattern:aaab
    value: aaaaaaaaaaaaaaaaab

    每一轮里面的for循环都会跑完,也就是最大的时间复杂度。
    所以可以考虑通过计算哈希的方法,比如计算模式串的哈希值,然后在主串中计算相同长度的哈希,如果相等表示匹配成功。
    注意哈希冲突

    RK算法全程Rabin-Karp,该算法的2位发明者Rabin和Karp的名字组合而成。该算法的核心思想就是通过比较2个字符串的hashcode来判断是否包含对方。

    计算哈希的方法有很多,
    (1)比如因为字母有26位,可以转化为26进制数。
    bedc = 2 *(26^3) + 5 * (26^2) + 4 * 26 + 3

    这样哈希冲突大大减小,但可能超出整型范围,需要进行取模。
    (2)可以使用按位相加,但是可能出现哈希冲突。
    注意:如果在主串中更新哈希值的过程中不做任何处理,相当于还是进行了O(mn)次,没有任何改进,所以每次更新哈希值可以将前一个字符剔除,后一个字符加入。

    // 虽然使用了哈希,复杂度还是O(mn)
    bool patternMatching(string pattern, string value) {
            int m = pattern.size();
            int n = value.size();
            int patternCode = hash(pattern);
            int strCode = hash(value.substr(0, m));
            for(int i = 0; i <= (n-m); i++){
                strCode = hash(value.substr(i,m));
                if(strCode == patternCode && compareString(i, value, pattern)){
                    return true;
                }
            }
            return false;
        }
        int hash(string str){
            int hashcode = 0;
            for(char c: str){
                hashcode += (c - 'a');
            }
            return hashcode;
        }
        bool compareString(int i , string s, string p){
            string temp = s.substr(i, i+p.size());
            return temp == p;
        }
    
    bool patternMatching(string pattern, string value) {
            int m = pattern.size();
            int n = value.size();
            int patternCode = hash(pattern);
            int strCode = hash(value.substr(0, m));
            for(int i = 0; i <= n-m; i++){
                if(strCode == patternCode && compareString(i, value, pattern)){
                    return true;
                } 
               if(i!= n-m) { //i+m <n, 计算下一轮的哈希
                    strCode = nextHash(value,strCode, i, i+m);
                }
            }
            return false;
        }
    
        int hash(string str){
            int hashcode = 0;
            for(char c: str){
                hashcode += (c - 'a');
            }
            return hashcode;
        }
        int nextHash(string s, int hash, int before, int next){
            hash -= (s[before] -'a');
            hash += (s[next] - 'a');
            return hash;
        }
        bool compareString(int i , string s, string p){
            string temp = s.substr(i, i+p.size());
            return temp == p;
        }
    

    BM

    字符串比较是从后往前。

    坏字符规则

    坏字符就是模式串和主串比较时,最后一个不匹配的字符。
    当监测到坏字符,不需要一位位移动,如果坏字符和模式串中某一个字符匹配,直接移动将他们匹配;
    在这里插入图片描述

    如果不相等直接移动:
    在这里插入图片描述
    看一个例子:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    注意⚠️: 查找模式串中是否存在坏字符,也是从右向左,找到第一个和坏字符匹配的字符串进行匹配。

     bool patternMatching(string pattern, string value) {
            int m = pattern.size();
            int n = value.size();
            int start = 0;
            while(start <= n-m){
                int i;
                for(i = m-1; i>=0; i--){
                    if(pattern[i]!= value[start+i]){
                        break;
                    }
                }
                if(i < 0) return true; // sucess;
                int charIndex = findCharacter(pattern, value[start+i], i);
                int off = charIndex == -1 ? i+1:i-charIndex;
                start += off;
            }
            return false;
        }
        int findCharacter(string pattern, char badCharacter, int index){
            for(int i = index-1; i>=0; i--){
                if(pattern[i] == badCharacter) return i;
            }
            return -1;
        }
    

    好后缀规则

    好后缀规则就是模式串中和字串中匹配的后缀
    在这里插入图片描述
    如果模式串中有相同的后缀,我们可以挪动模式串,让这个片段和好后缀对齐:
    在这里插入图片描述
    如果模式串中不存在和好后缀相同的片段,是否可以直接将模式串挪到好后缀之后??
    不可以
    不可以直接挪动整个的模式串,还需要判断模式串的前缀时候和好后缀的后缀匹配
    在这里插入图片描述

    什么时候使用坏字符,什么时候使用好后缀呢?
    每一轮进行计算,哪一种规则可以挪动的距离更多就使用哪一种。

    KMP

    kmp算法由三位科学家D.E.Knuth, J.H.Morris and V.R.Pratt提出,KMP这个算法名字就是取自三个人的姓氏首字母。
    整体思路:
    和BM类似,如果遇到坏字符,应该如何移动呢? 直接移动整个模式串? 当然不可以。应该利用已经匹配的字符串,是否主串的后缀和模式串的前缀相同,如果相同,重合移动,如果不同,直接移动整个串,看一个例子:
    发现坏字符A
    在这里插入图片描述
    注意:最长可匹配后缀字串, 最长可匹配前缀子串
    在这里插入图片描述
    挪动重合两个子串,发现新的坏字符
    在这里插入图片描述
    计算现在的最长可匹配前缀字串和后缀子串
    在这里插入图片描述
    挪动,进行下一轮比较:
    在这里插入图片描述

    以上就是KMP算法的整体思路:在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串,在下一轮直接把两者对齐,从而实现模式串的快速移动。

    那么如何计算最长可匹配后缀子串,最长可匹配前缀子串?

    我们可以提前缓存到一个数组中,这个集合就是next, 生成他就是最大的难点。

    next

    数组的下标表示已经匹配的前缀的下一个位置元素的值表示“最长可匹配前缀字串的下一个位置

    在这里插入图片描述
    next 数组的使用
    在这里插入图片描述
    next 数组的生成:
    设置变量i,j。 i 表示以匹配前缀的下一个位置,也就是数组下标。
    j表示最长可匹配前缀字串的下一个位置,也就是带填充的数组元素值。

    i = 0, j = 0
    next [i] = 0; i++

    在这里插入图片描述

    next[1] = 0, i++

    在这里插入图片描述
    判断如果pattern[j] != pattern[i-1], 即G!=T, 最长可匹配前缀字串不存在

    next[2] = 0; i++

    在这里插入图片描述

    判断pattern[j] == pattern[i-1]
    next[3] = next[2]+1; j++; i++

    在这里插入图片描述

    判断pattern[j] == pattern[i-1] ,
    next[4] = next[3]+1, j++; i++

    在这里插入图片描述

    判断pattern[j] == pattern[i-1] ,
    next[5] = next[4]+1, j++; i++
    在这里插入图片描述
    在这里插入图片描述
    继续i++,
    pattern[j] != pattern[i-1] ,这时候怎么办呢?

    在这里插入图片描述
    计算“GTGTGC” 最长可匹配前缀字串问题,转化为计算GTGC的最长可匹配的问题。
    在这里插入图片描述
    这样的问题转化,也就相当于把变量j回溯到了next[j],也就是j=1的局面(i值不变)
    在这里插入图片描述
    回溯之后pattern[j] != pattern[i-1] ,继续转化
    在这里插入图片描述

    依然是pattern[j] != pattern[i-1], j 不能回溯了,所以next[6] = 0;

    伪代码

     对模式串进行预处理,求出next 数组
     进入主循环,遍历主串
     		
     		比较主串和模式串的字符
     		如果发现坏字符,查询next 数组,得到匹配前缀所对应的最长可匹配前缀字串,移动模式串到对应的位置
    		如果当前字符匹配,那么继续循环
    
    class Solution {
    public:
        bool patternMatching(string pattern, string value) {
            int m = pattern.size();
            int n = value.size();
            next.resize(m+1);
            next[0] = 0; 
            next[1] = 0;
            getNext(pattern);
            int j = 0;
            for(int i = 0; i < value.size(); i++){
                while(j > 0 && value[i]!= pattern[j]) j = next[j];
                if(value[i] == pattern[j])j++;
                if(j == m) return true;
            }
            return false;
        }
        void getNext(string pattern){
            int j = 0, i = 2;
            for(; i < pattern.size(); i++){
                while(j!=0 && pattern[j]!=pattern[i-1]) j = next[j];
                if(pattern[j] == pattern[i-1])j++;
                next[i] = j;
            }
    
        }
    private:
        vector<int> next;
    };
    
    

    空间复杂度O(m), 时间复杂度O(m+n)

    展开全文
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • int BF(string S,string T) { int i=0; int j=0; while(i<S.length() && j<T.length()) { if(S[i]==T[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j>T.leng
  • 模式匹配是数据结构中字符串的一种基本运算,给定一个子串,即在某个字符串中找出与该子串相同的所有子串的过程。 例如,在主串S= "abcdacde" 中找出子串 T = "cd", 找到子串后返回在主串中子...
  • BF算法(朴素算法): 说明如下如所示: 实现效果如图: 源码如下: #include<...//初始化字符串链表 String* initString() { String* s=(String*)malloc(sizeof(String)); s->data=N
  • 找到临界值10-4=6的位置,ti-pi是文本正在匹配的子串的开始索引,当ti=7,pi=0时,没有比较的必要,立即退出 ti – pi 是指每一轮比较中 text 首个比较字符的位置,如8-2=6,符合要求,可以比较 ...
  • int index_BF(string S,string T,int pos) { //返回模式T在主S中第pos个字符之后第一次出现的位置 int i=pos; int j=0; while(i<S.length() && j<T.length()) { if(S[i]==T[j]) i++,j++; ...
  • 本文详细介绍两种最常见的字符串模式匹配算法:朴素模式匹配KMP模式匹配字符串模式匹配,也称子串的定位操作,通俗的说就是在一个主串中判断是否存在给定的子串(又称模式串),若存在,则返回匹配成功的索引。...
  • #include#include#include#definemax100...//简单模式匹配intIndex(SStringS,SStringT,intpos){//返回子串T在主S中第pos个字符之后的位置。//若不存在,则函数值为0。//其中,T非空,1≤pos≤StrLength(S)。int...
  • //字符串均以#开头,但#不算在字符串内容里 typedef struct{ char ch[100]; int length; }SString; void IndexBF(SString s,SString t); int main() { SString s,t; scanf("%s%s",s.ch,t.ch); s.leng...
  • c语言模式匹配BF

    千次阅读 2022-03-14 17:01:49
    使用c语言,顺序表存储形式实现BF算法
  • 目录 前言 一、算法逻辑 二、代码实现 总结 ...BF算法,即暴力(Brute Force)算法...bf算法进行字符串完全的遍历,所以其的时间复杂度较大,为(O(n * m)),但逻辑简单,代码实现方便。 一、算法逻辑 主串和子串从
  • 《C语言》字符串匹配BF算法+KMP算法)

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

    2021-05-21 08:21:37
    《数据结构(C语言版)》之“模式匹配算法”模式匹配算法 >>>1.定义的顺序存储结构。 >>>2.编写函数实现串# include # include # include # define OK 1 # define ERROR 0 typedef int ...
  • 实现字符串的常用匹配操作(BF算法),并介绍了改进的KMP算法实现
  • 话不多说,直接进入主题:         题目描述:给定两个... LeetCode字符串匹配的题目:https://leetcode-cn.com/problems/implement-strstr/         举个例子: 字符串tex
  • 字符串匹配算法有很多,我们先来介绍简单的BF算法,后面还有PK算法,BM算法,KMP算法等,我会一篇一篇和大家一块讨论。 BF算法的原理与实现 我们先来了解两个概念:主串和模式串,简单的说,如果在字符串a中查找...
  • 串模式匹配----BF算法

    2021-04-19 16:54:18
    这道题就是一个串模式匹配的问题,常见的相关算法有:BF(暴力算法),KMP算法,本文主要讲一下BF算法。 先给出本人的AC代码 class Solution { public int strStr(String haystack, String needle) { if (hays
  • 简单模式匹配,即两个字符串像物流传送带一般,主串固定,子串一步步像前移动,一位位匹配比较,直到完全匹配找到想要的结果的位置。 2.描述 简单模式匹配的原理如下: 从主串text[i]和字串pattern[j]开始向后遍历...
  • 字符串模式匹配算法的 Java 实现

    千次阅读 2019-02-21 20:28:39
    字符串匹配算法:检查模式P是否另一个字符串T(T代表文本)的子串,因为要检查整个定长的字符串P,所以有时这些算法称为精确字符串匹配算法。 蛮力法(BF算法) 对于文本T中的每个可能的位置,检查P是否匹配,...
  • BF改:当判断匹配失败的字符串是不是与首字母相同 若不同,继续BF算法; 若相同,直接将首字母移到当前位置 KMP:通过前缀与后缀发现待匹配字符串本身的特性,匹配失败时一次性移动多个字符以减少工作量 # ...
  • * bf字符串寻找算法 * 算法思想,使用子串对主串进行挨个匹配,如果匹配不正确,则主串向后加1,继续匹配 * 将待匹配的主串和子串做成字符数组,方便匹配使用 */ public class BfSearch { /** * 使用bf算法,...
  • BF算法,是一种简单朴素的模式匹配算法,常用于在一个主 S 内查找一个子串 T 的出现位置。 核心思想与操作是: 对于给定的主 S 与子串 P ,主 S 的长度为 N,子串 T 的长度为 M ; 首先,将 S[1] 和 T[1] ...
  • 字符串模式匹配--BF算法&KMP算法

    千次阅读 多人点赞 2018-04-05 13:58:59
    BF算法是基于主指针回溯,重新与子串进行逐字符进行比较,主为S什么要进行回溯呢,原因在于模式P中存在相同的字符或者说由字符)存在重复(模式的部分匹配性质),设想如果模式P中字符各不相同,主就S的...
  • 模式匹配(C语言实现)——BF算法

    千次阅读 多人点赞 2018-11-30 11:27:55
    模式匹配算法:子串的定位运算 算法思想: 设有主S,模式T。有 i 和 j 分别指向S和J的首个元素。(i=1;j=1;) 设有pos。pos指T在S中首次出现的位置的首地址。初始指向S的首元素。 将T中的首个元素与S中首个...
  • 模式匹配算法,通俗地理解,是一种用来判断两个之间是否具有"主与子串"关系的算法。...实现串模式匹配的算法主要有以下两种: 普通的模式匹配算法; 快速模式匹配算法; 本节,先来学习普通模式匹配BF...
  • 数据结构————串模式匹配BF

    千次阅读 2022-04-12 13:12:12
    字符串模式匹配是将两个A和B字符串进行比较,如果A字符串是B的子串,那么返回B在A串中出现的位置;如果不是子串,则返回错误。 那么BF算法就是最好想的算法,但是时间复杂度就会大一点。设置两个指针分别指向A和B...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,234
精华内容 2,093
关键字:

编写实现字符串模式匹配(bf)