精华内容
下载资源
问答
  • 对于数据结构中的章节,最为重要的莫过于模式匹配算法:即为求给定子在主中的出现的位置。从最开始的朴素模式匹配到后来的KMP算法,再到改良的KMP算法,算法逐渐改良,理解难度也逐渐加大。本人曾经多次...

    模式匹配算法

    前言

    对于数据结构中串的章节,最为重要的莫过于串的模式匹配算法:即为求给定子串在主串中的出现的位置。从最开始的朴素模式匹配到后来的KMP算法,再到改良的KMP算法,算法逐渐改良,理解难度也逐渐加大。本人曾经多次阅读相关内容,怪于自身理解能力有限仅一知半解,但心中甚为挂念。今再次读之理解更深入之,遂记之以铭后效。

    注解:

    本文字符串结构皆为顺序存储结构,且使用下标为0的数组分量表示字符串的长度
    主串标记为字符数组S,子串或者模式注为字符数组T


    朴素模式匹配算法

    //返回子串T在主串S中第pos个字符开始之后的位置。不存在返回0
    int Index(SString S,SString T,int pos)
    {
    	int i=pos,j=1;//i是主串的字符指针,j是模式的字符指针
    	while(i<=S[0]&&j<=T[0])
    	{
    		if(S[i]==T[j])//
    		{
    			i++;
    			j++;
    		}else{
    			i=i-j+2;//对i进行回溯,回溯到pos的后续位置
    			j=1;//j回溯到1
    		}
    	}
    	if(j>T[0])
    		return i-T[0];//返回子串在pos之后的第一个位置
    	else
    		return 0;//没有找到子串
    }
    

    算法思想步骤

    1. i为主串S的字符指针,j为模式的字符指针
    2. 令i指向pos代表的字符,j指向模式第一个字符
    3. 令S[i]和T[j]进行比较
      • 若相等,则i++,j++
      • 若不相等,i=i-j+2,j=1
    4. 转步骤[3]
    • 匹配成功:
      模式T中的每个字符依次和主串S中的一个连续字符序列相等。函数值为该对应相等连续字符序列中第一个字符在主串S中的位置
    • 匹配不成功:函数值返回0
    • 一般情况下的时间复杂度:O(m+n)
    • 最坏情况下的时间负责度:O(m*n)
    • 缺点:主串中存在多个与模式字符串“部分匹配”的子串,因此导致指针i的不断回溯

    KMP模式匹配算法

    改进的点:
    在每一趟匹配过程中出现字符串比较不相等时,不需要回溯指针i,而是利用已经匹配得到的结果,将模式尽可能向右滑动一段距离,继续比较。

    问题解决思路:

    1. 问:当主串和模式匹配过程出现不相等,该怎么办?
      答:避免将指针i回溯,i保持不动,尝试将模式进行右滑
    2. 问:将模式右滑的是指什么?
      答:i指针不变,找到下一个与i指针指向字符进行比较的模式中的字符
    3. 问:右滑的意义在哪?为什么要右滑?
      答:利用上轮匹配得到部分的“匹配结果”,提高查找模式串的效率,避免指针i不断回溯导致的效率低下,只要让j进行回溯就好
    4. 问:假设我们有匹配结果,即失配的j>1,那么上轮匹配得到的“匹配结果”是什么?
      答:假设是S[i]!=T[j]导致发生失配,则之前的匹配结果为:
      p 1 p 2 p i … p j − 1 = s i − j + i … s i − 1 . \begin{aligned}p_{1}p_{2}p_{i}\ldots p_{j-1}=s_{i-j+i}\ldots s_{i-1}\\ .\end{aligned} p1p2pipj1=sij+isi1.
    5. 问:如何利用部分“匹配结果”?
      答:假设存在: p 1 p 2 p i … p k − 1 ∈ p 1 p 2 p i … p j − 1 p_{1}p_{2}p_{i}\ldots p_{k-1}\in p_{1}p_{2}p_{i}\ldots p_{j-1} p1p2pipk1p1p2pipj1且有: S i − k + 1 S i − k + 2 … s i − 1 ∈ s i − j + i … s i − 1 S_{i-k+1}S_{i-k+2}\ldots s_{i-1}\in s_{i-j+i}\ldots s_{i-1} Sik+1Sik+2si1sij+isi1 并且有 p 1 p 2 p i … p k − 1 = S i − k + 1 S i − k + 2 … s i − 1 p_{1}p_{2}p_{i}\ldots p_{k-1}=S_{i-k+1}S_{i-k+2}\ldots s_{i-1} p1p2pipk1=Sik+1Sik+2si1
      则i指针下一个要与之比较的字符为模式中第k个字符
    6. 问:部分匹配结果和第k个字符的现实意义是什么?
      答:假设在模式第j个字符发生不匹配的状况,那么部分匹配结果的现实意义是在匹配了的字符串 p 1 p 2 p i … p j − 1 p_{1}p_{2}p_{i}\ldots p_{j-1} p1p2pipj1中的尽可能长且相等的前缀字符串和后缀字符串。
    7. 问:为什么是尽可长?
      答:尽可能利用已经匹配了的结果,并且减少模式右滑的距离,使i回溯的距离尽可能少。
    8. 问:假设之前已经匹配了的字符串中没有相等的前后缀字符串怎么办?
      答:那么就去令i指针指向的字符和模式字符串第一个字符做比较
    9. 问:为什么现在和模式第一个字符串做比较?
      答:假设有长度为1的前后缀子串,那么根据以上讨论,i指针接下来应该和模式第2个字符相比较,那么假设如果没有相等的前后缀,为了让模式右滑,则j指针只能回溯到1的位置。将i指针和模式第一个字符比较。
    10. 问:假设根本没有匹配部分怎么办?即跟模式串第一个字符比较就不相等,匹配部分都没有,根本谈不上寻找相等的前后缀子串!
      答:这个时候i并不回溯,直接后移1位,即**++i**,和模式串第1个字符开始进行匹配,j本身指向第一个字符,因此j=1保持不变。这里的处理办法跟朴素的模式匹配一样!
    11. 假设模式不右滑,并且还是像朴素的模式匹配算法一样i从pos后继开始,指针i和j重新开始从头依次比较,会发生什么情况?
      答:仍然假设是S[i]!=T[j]导致发生失配,此时让我们标记a=i,b=j,则之前的匹配结果为:
      p 1 p 2 p i … p j − 1 = s i − j + 1 … s i − 1 . \begin{aligned}p_{1}p_{2}p_{i}\ldots p_{j-1}=s_{i-j+1}\ldots s_{i-1}\\ .\end{aligned} p1p2pipj1=sij+1si1.
      则根据朴素的模式匹配算法,i=i-j+2,j=1,假设它们经过多次比较,发生2种情况:
    • i<a时,主串第i个字符和模式第j个字符发生了失配,导致重新执行朴素的模式匹配算法
    • i<a时,主串第i个字符和模式第j个字符都全部相等,当i==a时,主串第i个字符和模式第j(此时j<b)个字符进行比较,这不就是模式串右滑的场景吗?i保持不变,对j进行回溯,直接采用右滑模式串还可以省去从头开始的比较,这就是为什么采用模式右滑的KMP模式匹配算法更好

    引出next数组。

    若next[j]=k,则next[j]表明当模式串第j个字符和主串中某个字符比较缺“失配”时,在模式串中重新和该主串字符进行比较的字符的位置。
    由此我们可以定义: n e x t [ j ] = { 0 ( j = 1 ) max ⁡ { k ∣ 1 < k < j & p 1 … p k − 1 = p j − k + 1 … p 1 } 1 next\left[ j\right] =\begin{cases}0 \left( j=1\right) \\ \max \left\{ k| 1<k <j\& p_{1}\ldots p_{k-1}=p_{j-k+1}\ldots p_{1}\right\} \\ 1\end{cases} next[j]=0(j=1)max{k1<k<j&p1pk1=pjk+1p1}1

    则有:

    1. 当i=1时,next[1]=0;
      如果模式串中第1个字符就与主串字符不等。0表示,在i=1之前,没有匹配结果。那么直接将主串字符后移1位,重新和模式字符串第一个字符开始新的比较轮次。
    2. next[i]=1;
      对应模式串中第i个字符与主串字符不等,且之前的匹配结果中不存在相等的前缀和后缀字符串,那么直接将主串字符和模式串第1个字符去比较。
    3. next[i]=k;
      对应模式串中第i个字符与主串字符不等,之前的匹配结果中存在 p 1 p 2 p 3 … p k − 1 = p i − k + 1 … p i − 1 p_{1}p_{2}p_{3}\ldots p_{k-1}=p_{i-k+1}\ldots p_{i-1} p1p2p3pk1=pik+1pi1那么直接将主串字符和模式串第k个字符去比较。

    KMP模式匹配算法代码实现

    int Index_KMP(SString S,SString T,int pos)
    {
        int i=pos,j=1;//定义指向主串的i指针,和指向模式的j指针
        while(i<=S[0]&&j<=T[0])
        {   
            /*当S[i]==T[j],i和j都后移,然后继续比较后续字符
            j=0的情况为在i与j=1进行比较且不等的情况下,j=next[1]=0
            此时对应于与模式串第一个字符比较不等后,通过(i++)后移1位和模式第(++j)=1个字符重新开始比较的情况*/
            if(j==0|S[i]==T[j])
            {
                i++;
                j++;
            }else{
                //模式右滑,在S[i]!=T[j]的情况下,寻找下一个与第i个字符比较的模式中的第j个字符
                j=next[j]
            }
        }
    }
    

    那么问题来了!KMP算法的实现是在已知next数组的基础上,那么如何求的模式串的next数组呢!
    由以上讨论得知next数组只取决于模式串本身,而与待匹配的主串无关,我们可以从分析其定义出发用递归的方式逐渐求得next数组!!

    在此重申next数组的定义:
    对于next数组,next[j]表明当模式串第j个字符和主串中某个字符比较却不相等时,在模式串中重新和该主串字符进行比较的字符的位置。

    假设模式字符串的为: p 1 p 2 p i … p n p_{1}p_{2}p_{i}\ldots p_{n} p1p2pipn

    算法:如何求得next数组

    1. 对于任意模式串的next数组,当i=1时,默认next[1]=0;
      0表示,在i=1之前没有字符串相等的匹配结果。我们默认next[1]=0。
    2. 对于任意的模式串的next数组,当i=2时,默认next[2]=1;
      模式串中第2个字符与主串字符不等时,之前的匹配相等的字符串长度为1,此时长度为1的匹配结果不存在相等前缀和后缀子串的问题,我们默认next[2]=1。
    3. 假设已经存在next[i]=j;这表明在模式串中存在下列关系:
      p 1 … p j − 1 = p i − j + 1 … p i − 1 p_{1}\ldots p_{j-1}=p_{i-j+1}\ldots p_{i-1} p1pj1=pij+1pi1
      现在有next[i]=j,来递推next[i+1]为多少呢?
    • 若T[i]==T[j],则模式串中有: p 1 … p j = p i − j + 1 … p i p_{1}\ldots p_{j}=p_{i-j+1}\ldots p_{i} p1pj=pij+1pi
      则next[++i]=++j,相等的前缀和后缀子串长度扩张1
    • 若T[i]!=T[j],则模式串中有: p 1 … p j ! = p i − j + 1 … p i p_{1}\ldots p_{j}!=p_{i-j+1}\ldots p_{i} p1pj!=pij+1pi
      那么前缀和后缀子串无法扩张,只能收缩!k是衡量前缀长度的标志,k-1为相等的前后缀长度
      那么问题来了,我们应该在收缩的情况下,我们应该收缩多少呢?我们已经知道我们应该尽可能少的去收缩!以便我们提高匹配速度!对此问题,我们进行试探!

    假设我们收缩的大小为k,即假设next[i+1]=k(k<j),则必定有: p 1 … p k − 1 = p i − k + 2 … p i p_{1}\ldots p_{k-1}=p_{i-k+2}\ldots p_{i} p1pk1=pik+2pi
    已经next[i]=j,所以有: p 1 … p j − 1 = p i − j + 1 … p i − 1 p_{1}\ldots p_{j-1}=p_{i-j+1}\ldots p_{i-1} p1pj1=pij+1pi1
    因为k<j,所以会有: p 1 … p k − 1 = p i − k + 1 … p i − 1 p_{1}\ldots p_{k-1}=p_{i-k+1}\ldots p_{i-1} p1pk1=pik+1pi1
    因为 p i − k + 1 … p i − 1 ∈ p i − j + 1 … p i − 1 p_{i-k+1}\ldots p_{i-1}\in p_{i-j+1}\ldots p_{i-1} pik+1pi1pij+1pi1
    又因为 p 1 … p j − 1 = p i − j + 1 … p i − 1 p_{1}\ldots p_{j-1}=p_{i-j+1}\ldots p_{i-1} p1pj1=pij+1pi1
    所以有 p i − k + 1 … p i − 1 ∈ p 1 … p j − 1 p_{i-k+1}\ldots p_{i-1}\in p_{1}\ldots p_{j-1} pik+1pi1p1pj1
    又因为 p 1 … p k − 1 ∈ p 1 … p j − 1 p_{1}\ldots p_{k-1}\in p_{1}\ldots p_{j-1} p1pk1p1pj1
    所以 p 1 … p k − 1 p_{1}\ldots p_{k-1} p1pk1 p i − k + 1 … p i − 1 p_{i-k+1}\ldots p_{i-1} pik+1pi1 p 1 … p j − 1 p_{1}\ldots p_{j-1} p1pj1中的相等的前缀和后缀子串,k为其中相等前后缀+1
    因为next[j]是 p 1 … p j − 1 p_{1}\ldots p_{j-1} p1pj1中最长的相等前后缀长度+1,所以令k=next[j],即强缀收缩为next[j]

    求next数组的代码实现

    void get_next(SString T,int next[])
    {
        int i=1;
        next[1]=0;
        //默认任意的模式串第1个字符的next值为0
        //同时默认任意的模式串第2个字符的next值为1,
        //为了统一处理,i=1,j=0时,使用next[++i]=++j得到next[2]=1
        int j=0;
        while(i<T[0])
        {   
            //对于T[i]==T[j]的情况,前缀扩张+1,因为next[i]=j,所以next[++i]=++j
            //对于j==0的情况,经过不断的收缩,判断之前的匹配中没有任何相等的前后缀,因此next[++i]=++j=1
            if(j==0||T[i]==T[j])
                next[++i]=++j;
            else
                j=next[j];//j进行回溯,前缀收缩
        }
    }
    

    KMP算法优点

    • KMP模式匹配算法当且仅当模式串和主串之间存在许多部分匹配时才会更加具有优势
    • KMP最大特点时主串指针不需要回溯,整个匹配过程仅需从头到尾扫描一遍
    • 对于处理从外设输入的字符串很有效,可以边读入边匹配,无需回头重读

    改良的KMP模式匹配算法

    缺陷

    当主串中第i个字符和模式中第j个字符比较不相等时,即S[i]!=T[j],根据流程next[j]=k,主串第i个字符接下来应该和模式中第k=next[j]个字符进行比较,假如T[k]==T[j],那么S[i]!=T[k],早就知道不相等,这种比较是没有意义的。

    改进

    因为上述比较没有意义,所以可以省略。按照一般流程,既然S[i]!=T[k],我们令主串第i个字符接下来应该和模式中第next[k]个字符进行比较。所以为何不更加直接点呢!那么当T[k]==T[j],直接令next[j]=next[k],意思为:当S[i]!=T[j],因为next[j]=next[k],所以令令主串第i个字符直接和模式中第next[k]个字符进行比较,省略S[i]和T[k]比较的部分,直接比较S[i]和T[next[k]]。

    求取next数组的代码实现(改进后的)

    void get_next(SString T,int next[])
    {
        int i=1;
        next[1]=0;
        //默认任意的模式串第1个字符的next值为0
        //同时默认任意的模式串第2个字符的next值为1,
        //为了统一处理,i=1,j=0时,使用next[++i]=++j得到next[2]=1
        int j=0;
        while(i<T[0])
        {   
            //对于T[i]==T[j]的情况,前缀扩张+1,因为next[i]=j,所以next[++i]=++j
            //对于j==0的情况,经过不断的收缩,判断之前的匹配中没有任何相等的前后缀,因此next[++i]=++j=1
            if(j==0||T[i]==T[j])
           {
    			i++;
    			j++;
    			//若T[i]==T[j],在主串某字符和模式第i个字符比较不等的情况下,
    			//后续主串该字符和模式第j字符比较会比较多余,
    			//所以令next[i]=next[j],主串该字符直接和模式第next[j]字符比较。
    				next[i]=next[j];
    			else
    				next[i]=j;
    		}
            else
                j=next[j];//j进行回溯,前缀收缩
        }
    }
    

    后言

    模式匹配算法到此就差不多了,后续如果有学到新的相关更好的算法,本人会继续更新。
    文章可能文字过多,图片太少!因为算法过程和推理来自根据已有参考资料自己思考,本人画图能力有限,无法保证美观得体,符合我心,于是便放弃作图。
    本文虽然缺乏图片明确阐述算法,但逻辑上能够完整自洽,推理顺畅。总的来说,便于自己回顾和反思。但于其他读者而言,可能需要花点耐心和时间仔细阅读

    展开全文
  • 模式匹配算法

    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;
    }
    

    运行结果

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

     

    展开全文
  • 的朴素模式匹配算法的常用算法之前先了解下的定义很简单,就是由零个或多个字符组成的有限序列,又叫做字符的存储结构 的存储结构可简单分为两种,用顺序存储或者链式存储。 顺序存储可以...

    串的概念

    说串的常用算法之前先了解下串,串的定义很简单,串就是由零个或多个字符组成的有限序列,又叫做字符串。

    串的存储结构

    串的存储结构可简单分为两种,用顺序存储或者链式存储。
    顺序存储可以理解为用数组来进行储存,链式存储就是用链表进行存储,这两者的特点在之前的文章有讲过,这里不再赘述。

    串的朴素模式匹配算法

    在日常工作大家都有一个很常见的操作,复制一句话或者一个词,然后在全文搜索下它们出现在文章的哪个地方,这种子串的定位操作通常称做串的模式匹配,模式匹配算是串中最重要的操作之一。
    这里举一个大话数据结构中的一个例子:
    假设我们要从主串S=“goodgoogle”中,找到T=“google”这个子串的位置,我们通常需要下面的步骤。

    1. 主串S第一位开始,S与T前三个字母都匹配成功,但S第四个字母是d而T是g。第一位就匹配失败。
      来自大话数据结构
    2. 主串第二位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败。
      来自大话数据结构
    3. 主串S第三位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败
      大话数据结构
    4. 主串S第四位开始,主串S首字母是d,要匹配的T首字母是g,匹配失败
      大话数据结构
    5. 主串S第五位开始,S与T,6个字母全匹配,匹配成功
      大话数据结构
      整个流程其实就是对主串的每一个字符作为子串的开头,与要匹配的字符串进行匹配,然后对主串做大循环,对每个字符开头做T的长度的小循环,直到匹配成功或全部遍历完成为止。
      接下来看下具体的代码实现:
    /**
     * 串普通模式匹配
     */
    public class CommonStringTest {
        public static int indexOf(String s, String t) {
            char[] ss = s.toCharArray();
            char[] tt = t.toCharArray();
            int sLength = ss.length;
            int tLength = tt.length;
            /**
             * 1. 校验主串和子串为0的情况
             * 2. 校验子串和主串的长度大小
             * 3. for循环找是否能找到完全匹配的子串
             */
            if (sLength <= 0) {
                return tLength == 0 ? sLength : -1;
            } else {
                if (tLength <= 0) {
                    return 0;
                }
                /**
                 * 控制for循环长度,两者差值加1,加1就是为了如果两者相等也要比较
                 * 例如 两者长度差是3,那么就要循环四次
                 */
                int fsize = sLength - tLength + 1;
                for (int i = 0; i < fsize; i++) {
                    //找到主串和子串第一个位置相同的char
                    if (ss[i] != tt[0]) {
                        do {
                            ++i;
                        } while (i < fsize && ss[i] != tt[0]);
                    }
                    /**
                     * 找到后继继续遍历即可,后续遍历就是主串和子串都按顺序递增往后一一比对
                     */
                    if (i < fsize) {
                        //得到下一个要匹配的位置
                        int next = i + 1;
                        int var11 = next + tLength - 1;
                        /**
                         * 遍历,其余【目标字符串】,从var12开始
                         * 如果var10不越界,(小于var11,表示其余【目标字符串】的范围)
                         * 同时【源字符串】==【目标字符串】,则
                         * 自增,继续查找匹配
                         */
    
                        for (int var12 = 0 + 1; next < var11 && ss[next] == tt[var12]; ++var12) {
                            ++next;
                        }
                        //源字符串中匹配到目标字符串,匹配结束,返回索引位置
                        if (next == var11) {
                            return i;
                        }
                    }
                }
    
            }
    
    
            return -1;
        }
    
        public static void main(String[] args) {
            System.out.println(indexOf("12345678","456"));
        }
    }
    
    

    这种匹配方式,最好的情况是什么呢?那就是一开始就匹配成功,比如“googlegood”中去找“google”,时间复杂度为O(1),又例如“abcdefgoogle”中去找“google”。那么时间复杂度为O(n+m),其中n为主串长度,m为要匹配的子串长度。

    最坏的情况那就是每次匹配不成功都发生在主串的最后一个字符。例如一个前者49个“0”和1个“1”的主串,后面是9个”0“和1个“1”的的子串,在匹配时,每次都得T中字符循环到最后一位才发现,这种最坏情况的时间复杂度为O((n-m+1)*m)。

    朴素模式匹配的缺点就是每次匹配不上就要回溯到主串的下一个位置进行匹配,这样效率其实不高,下一章会讲解KMP算法,感受下好算法是如何提高时间复杂度的。

    展开全文
  • 一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下 主串s=ababcabcacbab 从串t=abcac 一般匹配方法如下图所示 代码如下 int index(string s,string t) {  int i=0,j=0;  int l1=s.length();  ...

    一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下

    主串s=ababcabcacbab

    从串t=abcac

    一般匹配方法如下图所示

    图片

    代码如下

    int index(string s,string t)
    {
        int i=0,j=0;
        int l1=s.length();
        int l2=t.length();
        while(i<=l1-1&&j<=l2-1)
        {
            if(s[i]==t[j])
            {
                ++i;
                ++j;
            }
            else
            {
                if(j==0)
                {
                    ++i;
                }
                else
                {
                    i=i-j+2;
                    j=0;
                }

            }
            //cout<<"i="<<i<<"j="<<j<<endl;
        }
        if(j>l2-1) return i-l2;
        else return 0;
    }

    这样算下来的时间复杂度是O(l1*l2),因为每次只要中间发生字符串s[i]和t[j]不相等,这种算法会把字符串t的索引置为0,而主串s也是从之前开始匹配的i加一个1,其实我们可以发现,中间有些比较是不必要的,比如从第三趟比较就可以看出主串中第4,5,8个字符串是‘b’,'c','a',(对应模式串中的第2,3,4个字符)。而模式串t中第一个字符是a,所以其实不需要和这几个字符相比较了,只需要将模式向右滑动3个字符即可。这样的匹配过程中,实际上主串i没有回溯,只是模式串的j在变化,就降低了时间复杂度为O(l1+l2),这也就是kmp算法。

    kmp算法每趟比较过程让模式串向后滑动一个合适的位置,这个合适的位置我们可以算出来,一般称这个位置叫next表。

    先写出next表的定义,接下来再解释为什么这样定义

     

    结合这个图来解释

    先说一下,上面两个图中的S0和T0分别代表的是两个穿的长度,真正的字符串都从下标1开始。

    1)当j=1时,也就是说模式串的第一个字符就与当前位置s对应的字符不同,此时主串的下标应该+1,再和模式串第一个字符进行比较;

    2)当两个串匹配到此处时,前j-1个字符都是匹配的,到了第j个字符就不同了,此时需要把字符串t向右移动max{k}个位置。

    这个k应该满足1<k<j并且p1...pk-1=pj-k+1...pj-1.k的值可能有多个,为了不使向右移动丢失可能的匹配,选择最大的一个k,也就是max{k},其最大值为j-1;

    3)除了上面两种情况,发生匹配时,主串指针i不回溯,在最坏情况下,模式串从第1个字符开始与主串第i个字符比较,以便不丢失可能的匹配。

    上面讲解的next函数表的定义,然后下面是求next函数表的代码以及实现kmp算法。篇幅有点长,转到下一篇讲。

     

    展开全文
  • 介绍   KMP算法是一种高效的字符串模式匹配算法,也就是俗称字符串查找算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时提出,KMP这个名字取自这三位的名字首字母。 内容 一、字符串模式匹配   有两个字符串T和P,...
  • 字符串模式匹配: \quad \quad设 S 和 T 是给定的两个串,在主串 S 中找到模式串 T 的过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现的位置,否则匹配不成功,返回 -1...
  • 模式匹配:在主中找到与模式相同的子串,并返回其所在位置。 算法思想 将主与模式长度相同的子串搞出来,挨个与模式对比 当子串与模式某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个...
  • 朴素的模式匹配算法(Brute-Force)又称为古典型的、有回溯的算法。 BF算法的思想就是将目标S的第一个字符与模式T的第一个字符进行匹配, 若相等,则继续比较S的第二个字符和T的第二个字符; 若不相等,则比较...
  • 模式匹配中,子串P称为模式,主S称为目标。 示例: 目标S:"Beijing" 模式P:"jin" 匹配结果 = 3(匹配位置从0开始) 求子位置的定位函数 Brute—Force 简称BF算法,亦称简单匹配算法。采用穷举的思想...
  • 本文详细介绍两种最常见的字符串模式匹配算法:朴素模式匹配KMP模式匹配字符串模式匹配,也称子串的定位操作,通俗的说就是在一个主串中判断是否存在给定的子串(又称模式串),若存在,则返回匹配成功的索引。...
  • KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法,同时前面的例子中也描述了子串移动位置的...
  • 数据结构(11)--模式匹配算法之BF、KMP算法

    万次阅读 多人点赞 2016-02-23 13:35:40
    参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 ...1.的存储 1.1定长顺序存储 的定长顺序存储(静态数组): #define MAXSTRLEN 255 // 用户可在255以内定义最大长 typedef unsigned ch...
  • 目录 前言 一、暴力解 二、KMP算法 1、算法思想 2、next数组求法 总结 前言 子串的定位通常称为模式匹配,题目的要求是:在主S中找到第一次出现完整子串T(T被称为模式)时的起始位置,没找到就返回-1。...
  • 本文主要讲述的三种模式匹配算法(主和模式中字符都存放在下标1-length中)。 一、简单模式匹配算法 1.算法思想 (1)定义i和j两个指针,i指向主,j指向模式,i=j=1; (2)i指向主最后一个元素的下一个...
  • 改进的字符串模式匹配算法——KMP操作前言一、一般的模式匹配算法二、KMP算法的基本思想1.一般方法的弊端2.解决想法3.数学解释4.next()详解(1)解剖next()函数总结 前言 关于什么是CMP操作,详情见 KMP算法 一...
  • 本文总结了数据结构与算法中字符的主要内容,重点介绍了KMP模式匹配算法
  • 实现的模式匹配的算法主要有以下两种:普通的模式匹配算法;快速模式匹配算法;本节,先来学习普通模式匹配(BF)算法的实现。BF算法原理普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个同另一个...
  • 字符串模式匹配指的是,找出特定的模式串在一个较长的字符串中出现的位置。朴素的模式匹配算法很直观的可以写出下面的代码,来找出模式串在一个长字符串中出现的位置。/*朴素的模式匹配算法功能:字符串的模式匹配...
  • 的定位操作通常称作的模式匹配,是各种处理系统中的最重要操作之一...算法的时间复杂度为O(m*n),算法如下://朴素的模式匹配算法,S为主,T为模式,即找S中有没有与T相同的字串int Index(char *S, cha...
  • 两种模式匹配算法

    2021-07-16 17:13:33
    顾名思义,朴素的模式匹配算法就是按照匹配的字符顺序每循环自增一来匹配模式。 int simple_StringMatching(string match,string target,int pos) { //match是模式,target是目标,pos是开始匹配的位置 ...
  • 模式匹配算法:子串的定位运算 算法思想: 设有主S,模式T。有 i 和 j 分别指向S和J的首个元素。(i=1;j=1;) 设有pos。pos指T在S中首次出现的位置的首地址。初始指向S的首元素。 将T中的首个元素与S中首个...
  • BF算法(暴力算法)--模式匹配算法

    千次阅读 2020-02-18 15:42:24
    模式匹配算法:是数据结构中字符的一种基本运算,给定一个子串,要求在某个字符中找出与该子串相同的所有子串,这就是模式匹配。用途:搜索引擎、拼写检查、语言翻译、数据压缩等。 BF算法: BF算法即暴力...
  • 暴力匹配,也称为简单匹配算法,采用穷举的思想,从主的第一个字符开始和模式串中第一个字符比较。 若相等,则依次比较后续字符,如果不相等,模式串回溯为第一个字符,从主的第二个字符开始重新和模式串比较,...
  • 串匹配算法

    2021-03-25 22:57:11
    串匹配算法主要来通过匹配来返回主(T)中与模式串(P)完全重合的子串位置,一般分为BF算法和KMP算法。 BF算法 BF算法被称为最简单直观串匹配算法,利用i、j分别遍历T和P,当对应字符匹配时i、j则继续向下...
  • 朴素模式匹配算法   BF算法为朴素模式匹配算法的经典,该算法的主要思想,从主的第一个字符与模式中的第一个字符进行比较,若相等则继续比较,若不相等则从主中不相等的位置与模式中的第一个字符进行比较...
  • 目录快查前言一、本文所用名词注解(有一定基础可跳过)二、模式匹配算法1.朴素模式匹配算法(就是暴力算)有基础也可以跳过三、改进的模式匹配算法--KMP算法(正文)1、字符的前缀、后缀和部分匹配值2、KMP...
  • 朴素模式匹配算法时间复杂度,精准版

    千次阅读 热门讨论 2021-04-09 17:12:29
    都别说了,听我的,我看了很多资料和大佬的blog,最后确认王道的那个视频错了 最好时间复杂度o(1) 最差时间复杂度o(mn)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,643
精华内容 14,257
关键字:

串的模式匹配算法思想