精华内容
下载资源
问答
  • 串的简单模式匹配算法
    千次阅读
    2020-08-08 19:41:45

    字符串朴素模式匹配算法

    一、朴素模式匹配算法(简单模式匹配算法)思想:

    将主串中与模式串长度相同的子串搞出来,挨个与模式串对比
    当子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串
    若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较
    最坏时间复杂度: O(nm)
    最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配
    比较好的情况:每个子串的第1个字符就与模式串不匹配

    二、代码实现

    方案一:

    //方案① 
    int Index(String S,String T){
    	int i,j;
    	int k=1;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=k;
    			j=1;
    			k++;
    		}
    	}
    	if(j>T.length){
    		return k;
    	}
    	else return 0;
    }
    

    方案二:

    //方案② 
    int Index(String S,String T){
    	int i,j;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=i-j+2;
    			j=1;
    		}
    	}
    	if(j>T.length){
    		return i-T.length;
    	}
    	else return 0;
    }
    
    更多相关内容
  • 模式匹配算法

    2021-09-14 15:52:00
    确定主中所含子串(模式串)第一次出现的位置(定位) 算法应用 搜索引擎,拼写检查,语言翻译,数据压缩等。 算法种类 BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的) KMP算法(特点:速度快)...

    目录

    算法目的

    算法应用

    算法种类

    BF算法

    代码实现

    运行结果

    KMP算法

    next数组

    代码实现

    运行结果


    算法目的

    确定主串中所含子串(模式串)第一次出现的位置(定位)

    算法应用

    搜索引擎,拼写检查,语言翻译,数据压缩等。

    算法种类

    • BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的)
    • KMP算法(特点:速度快)

    BF算法

    算法的思路是从S的每一个字符开始依次与T的字符进行匹配,采用穷举法的思路。

    如图,i 为主串的指向 ,j为子串的指向,当匹配失败是,i 和j需要进行回溯,规则如下:

    i = i - j + 2, j = 1

    即 i 指向主串的下一个字符,j 指向子串的第一个字符,一直到匹配成功或主串搜索完毕。

    代码实现

    需要说明的是,上面分析的是基于第一个元素的位置是1而言的,而我们实际编程的时候第一个字符的下标是0,索引回溯时有一点不同,但是主要思路还是不变的。

    #include <iostream>
    #include <string>
    using namespace std;
    
    int bfsearch(string s, string t)
    {
        int i,j = 0;
        while(i < s.size() && j < t.size())
        {
            if(s[i] == t[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i - j + 1; // 这里并不是 i = i - j + 2, 原因是实际编程时起始下标为 0 
                j = 0;
            }
        }
        if(j >= t.size())
        {
            return i - j;
        }
        else
        {
            return -1;
        }
    }
    
    void test01()
    {
        string s = "abcdefg";
        string t = "def";
        cout << "主串 s = " << s << endl;
        cout << "子串 t = " << t << endl;
        cout << "子串 t 在主串 s 的 " << bfsearch(s, t) << " 号位。(索引从 0 开始。)" << endl;
    }
    
    
    int main()
    {
        test01();
    
        system("pause");
        return 0;
    }

    运行结果

    对于主串 s 而言,第一个元素 a 的下标为 0,即 子串 def 在其的 3 号位,运行结果一致~

    KMP算法

    KMP算法是D.E.Kunth、J.H.Morris 和 V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,从而使算法效率有了某种程度的提高。利用已经部分匹配的结果而加快模式串滑动的速度,且主串S的指针i不避回溯!这样可将时间复杂度提升至O(n+m)! 

    主要思想就是若模式串中存在相等的前后缀,那么上一次匹配的后缀部分等同于下一次匹配的前缀部分,此时直接从相等的前缀部分的下一个字符开始匹配! 

    next数组

    • 前缀:包含首位字符但不包含末尾字符的子串
    • 后缀:包含末位字符但不包含首位字符的子串
    • next数组定义:当主串与模式串的某一位不匹配时,模式串要退回的位置
    • next[j]: 其值 = 第 j 位字符前面 j - 1 位字符串组成的子串的前后缀重合的字符数 +1
    • 复杂度:构造next数组算法的时间复杂度和空间复杂度均为O(n).

    代码实现

    #include <iostream>
    #include <string>
    using namespace std;
    
    // 获取next数组
    void getNext(int* next, const string& s)
    {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++)
        {
            while (j > 0 && s[i] != s[j])
            {
                j = next[j - 1];
            }
            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }
    }
    
    int kmpsearch(string s, string t)
    {
        if (t.size() == 0)
        {
            return 0;
        }
        int* next = new int[t.size()];
        getNext(next, t);
        int j = 0;
        int index = -1;
        for (int i = 0; i < s.size(); i++)
        {
            while(j > 0 && s[i] != t[j])
            {
                j = next[j - 1];
            }
            if (s[i] == t[j])
            {
                j++;
            }
            if (j == t.size())
            {
                index = i - t.size() + 1;
            }
        }
        delete[] next;
        next = nullptr;
        return index;
    }
    
    void test01()
    {
        string s = "abcdefg";
        string t = "def";
        cout << "主串 s = " << s << endl;
        cout << "子串 t = " << t << endl;
        cout << "子串 t 在主串 s 中的位置是:" << kmpsearch(s, t) << endl;
    }
    
    int main()
    {
        test01();
    
        system("pause");
        return 0;
    }
    

    运行结果

     与预想结果一致,但是现在好像还没有考虑到在主串中重复存在模式串的情况,或者是默认只匹配一次!所以算法仍需改进!

     

    展开全文
  • 简单模式匹配算法(BF算法)、KMP算法

    一、简单的模式匹配算法(BF算法)

    在实际应用中我们常常能用到类似串的模式匹配,也称子串的定位操作。例如单词查找,百度搜索都是串的模式匹配操作。

    字符串模式匹配: 在主串中找到与模式串相同的⼦串,并返回其所在位置。

    • ⼦串——主串的⼀部分,⼀定存在;
    • 模式串——不⼀定能在主串中找到。

    例如:主串为:‘abaabaabcabaa’,模式串:‘baabc’;算出⼦串第⼀个字符的位置。

    【逻辑分析】: 算出主串中有多少个子串, 模式串与子串进行匹配;子串与模式串从第一个开始匹配,当他们的第一个相等,就接着匹配下一个,知道模式串匹配成功或者失败,最后返回结果。
    子串:{abaab,baaba,aabaa,abaab,baabc,aabca,bcaba,cabaa};
    模式串baabc

    易知:当匹配到第5个子串时,匹配成功,返回子串第一个字符的位置。在循环匹配中,模式串始终是从第一个字符开始匹配;而主串是当子串匹配不成功时+1,再匹配的。


    在很多场景中,主串远比模式串长得多,即n>>m。
    匹配成功的最好时间复杂度: O(m) ;
    匹配失败的最好时间复杂度: O(n-m+1) = O(n-m)=O(n);
    匹配失败的最坏时间复杂度:O(n*m)。


    int Index(SString S, SString T, int pos)
    {
    	//返回模式串T在主串S中第pos个字符之后第S一次出现的位置。若不存在,则返回值为0
    	//其中,T非空,1≤pos≤StrLength(S)
    	int i = pos;
    	int j = 1;
    	while(i<=S.length && j<=T.length)
    	{
    		if(S[i]==T[j])
    		{
    			++i;
    			++j;
    		} //继续比较后继字符
    		else
    		{
    			i=i-j+2;
    			j=1;
    		} //指针后退重新开始匹配
    	}
    	if (j>T.length)
    		return i-T.length;
    	else
    		return 0;
    }
    

    完整代码:

    /***字符串匹配算法***/
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255   		//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1];		//0号单元存放串的长度
    
    Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
    		T[0] = strlen(chars);	//char长度赋给T[0]
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);  //char的值赋给字符串T
    		return OK;
    	}
    }
    
    //算法4.1 BF算法
    int Index(SString S, SString T, int pos)
    {
    	//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在,则返回值为0
    	//其中,T非空,1≤pos≤StrLength(S)
    	int i = pos;
    	int j = 1;
    	while(i <= S[0]&&j <= T[0])
    	{
    		if(S[i]==T[j])
    		{
    			++i;
    			++j;
    		} //继续比较后继字符
    		else
    		{
    			i=i-j+2;
    			j=1;
    		} //指针后退重新开始匹配
    	}
    	if (j > T[0])
    		return i - T[0];
    	else
    		return 0;
    	return 0;
    }//Index
    
    int main()
    {
    	SString S;	//S串为主串
    	StrAssign(S,"abaabaabcabaa") ;
    	SString T;	//T串为模式串;
    	StrAssign(T,"baabc") ;
    	cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配\n";
    	return 0;
    }
    

    在这里插入图片描述

    二、KMP算法

    上面的BF算法中频繁的重复比较相当于模式串在不断地进行自我比较,导致其效率低下。我们不得不思考有没有更高校的方法。

    我们不想要主串回溯操作,利用部分匹配直接跳转到还没进行匹配的字符那里。

    next数组: 当模式串的第j个字符匹配失败时,令模式串跳到next[j]再继续匹配。

    当子串和模式串不匹配时,主串指针i不回溯,模式串指针j=next[j]。

    KMP算法,最坏时间复杂度 O(m+n);其中,求 next 数组时间复杂度 O(m),模式匹配过程最坏时间复杂度 O(n)。

    /***字符串匹配算法***/
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status;
    #define MAXSTRLEN 255 	//用户可在255以内定义最长串长
    typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度
    
    Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T
    	int i;
    	if (strlen(chars) > MAXSTRLEN)
    		return ERROR;
    	else {
    		T[0] = strlen(chars);
    		for (i = 1; i <= T[0]; i++)
    			T[i] = *(chars + i - 1);
    		return OK;
    	}
    }
    //计算next函数值
    void get_next(SString T, int next[])
    { //求模式串T的next函数值并存入数组next
    	int i = 1, j = 0;
    	next[1] = 0;
    	while (i < T[0])
    		if (j == 0 || T[i] == T[j]) 
    		//根据模式串T,求出next数组
    		{
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else
    			j = next[j];
    }//get_next
    
    //KMP算法
    int Index_KMP(SString S, SString T, int pos, int next[])
    { 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
    	//其中,T非空,1≤pos≤StrLength(S)
    	int i = pos, j = 1;
    	while (i <= S[0] && j <= T[0])
    		if (j == 0 || S[i] == T[j]) // 继续比较后继字
    		{
    			++i;
    			++j;
    		}
    		else //利⽤next数组进⾏匹配(主串指针不回溯)
    			j = next[j]; // 模式串向右移动
    	if (j > T[0]) // 匹配成功
    		return i - T[0];
    	else
    		return 0;
    }
    
    int main()
    {
    	SString S;
    	StrAssign(S,"aaabbaba") ;
    	SString T;
    	StrAssign(T,"abb") ;
    	int *p = new int[T[0]+1]; // 生成T的next数组
    	get_next(T,p);
    	cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    	return 0;
    }
    
    展开全文
  • 模式匹配算法(KMP算法,BF算法+算法详解+实现代码) 子串的定位操作是找子串在主中从第pos个字符后首次出现的位置,又被称为的模式匹配 一、BF模式匹配算法 BF算法思想:Brute-Force算法又称蛮力匹配算法...

    串的模式匹配算法(KMP算法,BF算法+算法详解+实现代码)

    子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置,又被称为串的模式匹配

    一、BF模式匹配算法

    • BF算法思想:Brute-Force算法又称蛮力匹配算法(简称BF算法),从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则继续比较后续字符;否则回溯到主串S的第pos+1个字符开始重新和模式串T进行比较。以此类推,直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等,则称模式匹配成功,此时返回模式串T的第一个字符在主串S中的位置;否则主串中没有和模式串相等的字符序列,称模式匹配不成功。

    • BF算法思想:
      从主串S的第pos个字符开始的子串与模式串T比较的策略是从前到后依次进行比较。因此在主串中设置指示器i表示主串S中当前比较的字符;在模式串T中设置指示器j表示模式串T中当前比较的字符。

    • 实例分析:
      给定主串为S=“ababcabcacbab”,T=“abcac”。匹配过程如下
      在这里插入图片描述

    • 实现代码:

    //BF模式匹配算法
    int Index(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    	}
    	if (j > T.len) {//匹配成功时,返回匹配起始位置
    		return i - T.len;
    	}
    	else {//匹配失败,返回0
    		return 0;
    	}
    }
    
    • 算法分析:
      • BF算法的思想比较简单,但当在最坏情况下,算法的时间复杂度为O(n*m),其中n和m分别是主串和模式串的长度。这个算法的主要事件耗费在失配后的比较位置有回溯,因而比较次数过多。为降低时间复杂度可采用无回溯的算法。

    二、KMP模式匹配算法(重点)

    • KMP算法思想
      Knuth-Morris-Pratt算法(简称KMP),是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法。KMP算法是模式匹配中的经典算法,和BF算法相比,KMP算法的不同点是消除BF算法中主串S指针回溯的情况,从而完成串的模式匹配,这样的结果使得算法的时间复杂度仅为O(n+m)。
    • KMP算法描述
      KMP算法每当一趟匹配过程中出现字符比较不相等时,主串S的i指针不需要回溯,而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后,继续进行比较 。
    • next函数
      在实现算法之前,我们需要引入next函数:若令next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的当前字符的位置。由此引出next函数的定义:
      在这里插入图片描述
      由此可见,next函数的计算仅与模式串本身有关,和主串无关。其中’T1T2…T(k-1)'时’T1T2…T(j-1)'的真前缀子串,
      ‘T(j-k+1)T(j-k+2)…T(j-1)’是’T1T2…T(j-1)'的真后缀子串。当next函数定义中的集合不为空时,next[j]的值等于串’T1T2…T(j-1)'的真前缀子串和真后缀子串相等时的最大子串长度+1
      通过以上分析,推导出模式串"abaabcac"的next值的计算过程如下表所示.
      (1).当j=1时,由定义得知,next[1]=0;
      (2)当j=2时,满足1<k<j的k值不存在,由定义得知next[2]=1;
      在这里插入图片描述
      则我们可以得出next值
      在这里插入图片描述
    • 匹配过程如下:
      在求得模式串的next函数之后,匹配可按如下进行:假设指针i和j分别指示主串S和模式串T中当前比较的字符,令i的初始值为pos,j的初值为1。若在匹配过程中Si=Tj,则i和j分别增1;否则,i不变,而j退到next[j]位置再比较(即Si和Tnext[j]进行比较),若相等,则指针各自增1,否则j再退到下一个next值得位置,以此类推,直至下列两种可能:
      第一种:j退到某个next值(next[…next[j]])时字符比较相等,则指针各自增1继续进行匹配;
      第二种是j退到next值为0(即与模式串得第一个字符失配),则此时需将主串和模式串同时向右滑动一个位置(此时j=0,当向右滑动一个位置时,即模式串得第一个字符),即从主串得下一个字符Si+1和模式串T1重新开始比较。

      在这里插入图片描述
    • 求next[]的算法如下:
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    

    三、改进的KMP算法

    我们在前面介绍的next函数虽然好用,但还不够完美,在某种情况下是有缺陷的,例如如下匹配过程
    主串为"aaabaaaab" 模式串为"aaaab"
    在这里插入图片描述

    在求得模式串的next值之后,匹配过程如下:
    在这里插入图片描述
    从串的匹配过程可以看到,当i=4,j=4时,S4!=T4,由next[j]所示还需进行i=4、j=3,i=4、j=2,i=4、j=1这三次比较。实际上,因为模式串中的第1、2、3个字符和第4个字符都相等(即都是’a’),因此,不需要再和主串中第4个字符相比较,而可以直接将模式串一次向右滑动4个字符的位置直接进行i=5、j=1的判断。
    这就是说,若按上述定义得到next[j]=k,而模式串中T(j)!=T(k),则当Si != Tj时,不需要进行Si和Tk的比较,直接和Tnext[k]进行比较;换句话说,此时的next[j]的值应和next[k]相同,为此将next[j]修正为nextval[j]。而模式串中Tj !=Tk,则当Si !=Tj时,还是需要比较Si和Tk的比较,因此nextval[j]的值就是k,即nextval[j]得值就是next[j]的值。
    通过以上分析,计算第j个字符得nextval值时,要看第j个字符是否和第j个字符的next值指向的字符相等。若相等,则nextval[j]=nextval[next[j]];否则,nextval[j]=next[j]。
    由此推导出模式串T='aaaab’的nextval值的计算过程如下:

    • 当j=1时,由定义知,nextval[1]=0;
    • 当j=2时,由next[2]=1,且T2=T1,则nextval[2]=nextval[1],即nextval[2]=0;
    • 当j=3时,由next[3]=2,且T3=T2,则nextval[3]=nextval[2],即nextval[3]=0;
    • 当j=4时,由next[4]=3,且T4=T3,则nextval[4]=nextval[3],即nextval[4]=0;
    • 当j=5时,由next[5]=4,且T5不等于T4,则nextval[5]=next[5],即nextval[5]=4.
      则模式串"aaaab"的nextval函数值如下所示。
      在这里插入图片描述
    • 改进后的匹配过程如下:
      在这里插入图片描述
      可以看到匹配次数大大减少,降低了复杂度。
    • nextval函数实现代码如下
      nextval[]时基于next[]函数实现的。
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    void Get_NextVal(HString T, int next[], int nextval[]) {
    	int j = 2, k = 0;
    	Get_Next(T, next);
    	nextval[1] = 0;
    	while (j <= T.len) {
    		k = next[j];
    		if (T.ch[j] == T.ch[k]) {
    			nextval[j] = nextval[k];
    		}
    		else {
    			nextval[j] = next[j];
    		}
    		j++;
    	}
    }
    

    通常,模式串的长度m比主串的长度n小很多,且计算next或者nextval函数的时间复杂度为O(m)。因此,对于整个匹配算法来说,所增加的计算next或nextval时值得的。
    BF算法的时间复杂度为O(m*n),但是实际接近于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下,才会比BF算法快。KMP算法的最大特点就是主串的指针不需要回溯,整个匹配过程中,主串仅需从头到尾扫描一次,对于处理从外设输入的庞大文件很有效,可以边读边匹配。

    四、KMP以及BF的完整代码实现。(Visual Studio 2017开发环境)

    头文件:DString.h

    #pragma once
    #include<windows.h>
    typedef struct {//堆串存储结构
    	char *ch;//若是非空串,则是指向串的起始地址;否则为空
    	int len;//字符串的长度
    }HString;
    //串初始化函数
    void HStrInit(HString *S) {
    	S->ch = NULL;
    	S->len = 0;
    }
    //串赋值函数
    int HStrAssign(HString *S, const char *chars) {
    	int i = 0;
    	if (NULL == chars || NULL == S) {
    		return 0;
    	}
    	else {
    		while (chars[i] != '\0') {
    			i++;
    		}
    		S->len = i;//串S的长度等于串chars的长度
    		if (0 != S->len) {
    			if (S->ch != NULL) {
    				free(S->ch);
    			}
    			S->ch = (char *)malloc(sizeof(char)*(S->len + 1));//0号单元不用,故比实际需求多开辟一个空间
    			if (NULL == S->ch) {//空间开辟失败
    				return 0;
    			}
    			for (i = 1; i <= S->len; i++) {//将chars的内容逐一赋值给S->ch
    				S->ch[i] = chars[i - 1];
    			}
    		}
    		else {
    			S->ch = NULL;//当chars的长度为0时,则置S为空串。
    		}
    		return 1;
    	}
    }
    //打印
    void print(HString *S) {
    	for (int i = 1; i <= S->len; i++) {
    		printf("%c", S->ch[i]);
    	}
    	printf("\n");
    }
    //BF模式匹配算法
    int Index(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    	}
    	if (j > T.len) {//匹配成功时,返回匹配起始位置
    		return i - T.len;
    	}
    	else {//匹配失败,返回0
    		return 0;
    	}
    }
    //统计BF模式匹配算法的比较次数
    int IndexCount(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	int count = 0;
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    		count++;
    	}
    	return count;
    	
    }
    //KMP模式匹配算法
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    void Get_NextVal(HString T, int next[], int nextval[]) {
    	int j = 2, k = 0;
    	Get_Next(T, next);
    	nextval[1] = 0;
    	while (j <= T.len) {
    		k = next[j];
    		if (T.ch[j] == T.ch[k]) {
    			nextval[j] = nextval[k];
    		}
    		else {
    			nextval[j] = next[j];
    		}
    		j++;
    	}
    }
    int Index_KMP(HString S, int pos, HString T,int nextval[]) {
    	int i = pos;//主串从第pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
    			++i;
    			++j;
    		}
    		else {
    			j = nextval[j];
    		}
    	}
    	if (j > T.len) {//匹配成功
    		return i - T.len;//返回匹配的起始位置
    	}
    	else {
    		return 0;
    	}
    }
    //统计KMP算法的比较次数
    int Index_KMPCount(HString S, int pos, HString T, int nextval[]) {
    	int i = pos;//主串从第pos开始
    	int j = 1;//模式串从头开始
    	int count = 0;
    	while (i <= S.len&&j <= T.len) {
    		if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
    			++i;
    			++j;
    		}
    		else {
    			j = nextval[j];
    		}
    		count++;
    	}
    	return count;
    }
    
    

    源文件:

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include"DString.h"
    int main() {
    	HString S;
    	HString T;
    	HStrInit(&S);
    	HStrInit(&T);
    	char a[] = "aaabaaaab";
    	char b[] = "aaaab";
    	HStrAssign(&S, a);
    	HStrAssign(&T, b);
    	printf("主串:");
    	print(&S);
    	printf("模式串:");
    	print(&T);
    	printf("BF模式匹配:\n");
    	int index = Index(S, 1, T);
    	int count1 = IndexCount(S, 1, T);
    	printf("index=%d\n", index);
    	printf("比较次数:%d\n", count1);
    	printf("KMP模式匹配:\n");
    	int *next,*nextval;
    	next = (int *)malloc(sizeof(int)*(T.len + 1));
    	nextval = (int *)malloc(sizeof(int)*(T.len + 1));
    	Get_NextVal(T,next,nextval);
    	printf("next[]数组如下\n");
    	for (int i = 1; i < (T.len + 1); i++) {
    		printf("%d ", next[i]);
    	}
    	printf("\nnextval[]数组如下:\n");
    	for (int i = 1; i < (T.len + 1); i++) {
    		printf("%d ", nextval[i]);
    	}
    	printf("\n");
    	int index1 = Index_KMP(S, 1, T, next);
    	int count2 = Index_KMPCount(S, 1, T, nextval);
    	printf("index1=%d\n", index1);
    	printf("比较次数:%d\n",count2);
    
    
    
    	system("pause");
    
    
    
    
    
    
    
    
    
    
    
    	return 0;
    }
    

    五、测试结果如下

    在这里插入图片描述

    展开全文
  •  BF算法是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较...
  • 目录简单模式匹配算法简单模式匹配算法完整实现代码运行结果KMP算法 简单模式匹配算法 简单模式匹配 Brute-Force(布鲁斯-福斯)算法是一种带回溯的匹配算法,算法的基本思想是:从主 s 的第一个字符开始...
  • 但考虑到存储效率和算法的方便性,多采用顺序存储结构。 1、的顺序存储 1)的定长顺序存储结构 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储值的字符序列按照预定义的大小,为每个定义的...
  • 文章目录BF算法、KMP算法BF算法算法过程算法代码的定义算法设计完整代码算法总结KMP算法算法过程next数组next数组的公式next数组程序代码算法代码...Brute-Force算法与Knuth-Morris-Pratt算法都是解决模式匹配
  • 全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
  • 数据结构---模式匹配算法介绍

    万次阅读 多人点赞 2017-02-21 19:26:05
    对于文本程序来说,找出一个子串在文本中的位置是特别重要的,我们称那个子串为模式(pattern),然后我们称寻找的过程为:模式匹配(string match)。 2、实现算法(1)—朴素字符串匹配算法 原理:从
  • KMP模式匹配算法 简述 为了解决朴素模式匹配算法的低效 kmp模式匹配算法由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的...
  • KMP字符串模式匹配通俗点说就是一种在一个字符中定位另一个的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
  • 的朴素模式匹配算法的常用算法之前先了解下的定义很简单就是由零个或多个字符组成的有限序列,又叫做字符的存储结构 的存储结构可简单分为两种,用顺序存储或者链式存储。 顺序存储可以...
  • 模式匹配算法 – BF算法详解

    千次阅读 2020-03-19 22:13:01
    BF算法是一种蛮力算法,其实现过程没有任何技巧,就是简单粗暴地拿一个同另一个中的字符一一比对,得到最终结果。 算法目的:确定主中所含子串第一次出现的位置,这里的子串也称为模式串。 设计思想: (1...
  • 子串的定位操作通常称作的匹配模式(其中P,T称为模式串,PaTtern),是各种处理系统中最重要的操作之一。...Brute—Force 简称BF算法,亦称简单匹配算法。采用穷举的思想。 具体思路: 初始时让目标 S ...
  • 实验题3:实现顺序的各种模式匹配算法 目的:掌握模式匹配算法(BF和KMP算法)设计。 内容:编写一个程序exp4-3.cpp,实现顺序的各种模式匹配算法,并在此基础上完成以下功能。 (1)建立目标s=...
  • 》》一种简单模式匹配算法:从主 S指定的字符开始(一般为第一个)和模式 T的第一个字符比较, 若相等,则继续逐个比较后续字符,直到 T中的每个字符依次和 S中的一个连续的字符序列相等,则 称匹配成功...
  • 数据结构——(朴素的模式匹配算法、KMP模式匹配算法) 键盘上的钢琴师_v5 提示:以下内容不适合零基础人员,仅供笔者复习之用。 概要: 是由零个或多个字符组成的有限序列,又名叫字符。 一、的比较 ...
  •   的模式匹配即子串定位是一种重要的运算。设s和t是给定的两个,在...简单模式匹配算法 KMP算法 简单模式匹配算法:   算法思想:首先将s1与t1进行比较,若不同,就将s2与t1进行比较,…,直到si和t1...
  • 这篇文章主要介绍了数据结构中的字符以及有关字符的很重要的算法——模式匹配算法,重点介绍了KMP算法的实现原理。
  • 数据结构——模式匹配算法

    千次阅读 2017-05-10 18:11:09
    2、模式匹配算法  的查找操作也称作的模式匹配操作,模式匹配操作的具体含义是:在主(也称作目标)中,从位置start开始查找是否存在子串(也称作模式),如在主中查找到一个与模式相同的子串,...
  • 今天主要想总结一下字符中的一个经常出现于教材的一个经典算法,算法的要求很简单,就是给出两个字符,判断一个字符是否是另一个字符的子串.子串的定位操作通常也叫做模式匹配.在算法教材中,我们通常把这两个...
  • 一、对一个中的某子串的定位操作称为 模式匹配; 二、模式:待定位的子串 三、基本思想:从主中的第一个位置起和模式的第一个字符开始比较 如果相等,则继续比较后续字符;...//简单模式匹配...
  • 串模式匹配问题算法介绍 算法目的: 确定主中所含子串(模式)第一次出现的的位置...Brute-Force简称为BF算法,亦称为简单匹配算法,采用穷举的思想。 S:a a a a b c d 主:正文 T: a b c 子串:模式 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,265
精华内容 38,106
关键字:

串的简单模式匹配算法