精华内容
下载资源
问答
  • 串的模式匹配算法

    2021-01-13 19:43:47
    串的模式匹配算法串的模式匹配算法朴素匹配 串的模式匹配算法 朴素匹配 这里采用C语言编写,使用串的定长存储,定义如下: // 顺序串的最大串长 #define MAX_STR_LEN 255 // 0号单元存放串的长度 typedef ...

    串的模式匹配算法

    串的模式匹配算法

    朴素匹配

    这里采用C语言编写,使用串的定长存储,定义如下:

    
    // 顺序串的最大串长
    #define MAX_STR_LEN 255       
    
    // 0号单元存放串的长度
    typedef unsigned char SString[MAX_STR_LEN + 1];      
     
    

    基本思想:从主串的第pos个字符开始,和模式串的第一个字符依次比较,若相同,则往后逐个比较模式串后续字符。若不等,则从珠串的下一个字符开始从头和模式串的字符相匹配。时间复杂度:最好情况下是O(n+m);最坏时间复杂度为O(n*m),在匹配01串的时候往往效率会比较低。

    算法实现如下:

    
    int Index(SString  S,SString T,int post=1) {
        int i =post;
        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]+1;
        return 0;
    }
    
    
    展开全文
  • 朴素的模式匹配算法 一个例子: 从主 S = "goodjob"中,找到子串 T = "job"的位置。我们通常需要下面的步骤。 1. 将子串"job"与主S从第一位对应匹配。即判断 whether 'g' == 'j'; 2. 判断结果为否,继续匹配 ...

    朴素的模式匹配算法

    一个例子:

    从主串 S = "goodjob"中,找到子串 T = "job"的位置。我们通常需要下面的步骤。

    1. 将子串"job"与主串S从第一位对应匹配。即判断 whether 'g' == 'j';
    2. 判断结果为否,继续匹配 whether 'o' == 'j';
    3. 直到找到第一位匹配 'j' = 'j';
    4. 继续匹配完整 S[4:7] == 'job' == T。
    

    是一种最简单的匹配算法,暴力易实现,但有许多冗余的步骤。

    KMP 模式匹配算法

    总的思想是:通过字符串已有的信息来规避朴素模式匹配中可以省略的步骤。

    详细的过程不再赘述,在这里只进行简要的说明。

    已知主串的下标为 ii, 子串的下标为 jj, 总结下来是两短句:“ii 不回溯,jjnextnext”。

    ii 不回溯:指的是在匹配过程中,主串的匹配下标永远只会增加或不变,不会再去匹配之前主串的下标。

    jjnextnext:指的是子串的下标匹配规则是依照nextnext 数组值。

    那么下面要详细说明nextnext 数组值是什么。

    nextnext 数组值推导

    先给出数学式的定义:
    next[j]={0,当 j = 1时Max{k1<k<jp1...pk1=pjk+1...pj1}1其他情况 next[j] = \begin{cases} 0, & \text{当 j = 1时} \\[2ex] Max\{ k | 1<k<j,且'p_1 ...p_{k-1}' ='p_{j-k+1}...p_{j-1}'\}& \text当此集合不空时\\[2ex] 1, & \text{其他情况} \end{cases}
    e.g. T = “abcabx”
    j123456Tabcabxnext[j]011123 \begin{array}{c|lcr} j & 123456 \\ \hline 模式串T & abcabx \\ next[j] & 011123 \end{array}
    其中的一个子串"abcab", abcab,前缀和后缀有两个字符相等,则 next[6]=2+1=3next[6] = 2 + 1 = 3

    整个算法的时间复杂度时 O(n + m),相较于朴素模式匹配算法的 O((n - m + 1) * m)来说,较好一些(T的长度为m)。

    KMP模式匹配算法改进

    一个例子:主串S = “aaaabcde”,子串T = “aaaaax”,其 next 数组值分别为 012345,在开始时,当 i = 5, j = 5时,我们发现"b" 与 "a"不想等,因此,j = next[5] = 4,此时 "b"与第四位置的"a"依然不等,j = next[4] = 3 … 这样也会多出很多冗余的步骤。所以,我们对求解next函数进行了改进。

    在每次赋值next的时候增加一个判断,判断 whether T[i]==T[j]whether\ T[i] == T[j]

    最后给出具体的python求解next数组的程序:

    import numpy as np
    
    def get_nextval(T):
        T = '#' + T
        i = 1
        j = 0
        nextval = np.zeros(len(T), dtype=int)
        
        while i < len(T)-1:
            if j == 0 or T[i] == T[j]:
                i = i + 1
                j = j + 1
                if T[i] != T[j]:
                    nextval[i] = j
                else:
                    nextval[i] = nextval[j]
            else: 
                j = nextval[j]
        nextval = np.delete(nextval,0)
        return nextval
    

    ----------------
    该文章首发于 zyairelu.cn
    欢迎来到我的网站进行评论及研讨
    个人邮箱zyairelu@gmail.com
    ----------------

    展开全文
  • 串的模式匹配在串的各种操作中是经常用到的算法。串的模式匹配也成为子串的定位操作,即查找子串在主串中出现的位置。本文主要讲解串的经典模式匹配算法—Brute-Force。 1 基本思想 串的模式匹配也称为子串的...

        串的模式匹配在串的各种操作中是经常用到的算法。串的模式匹配也成为子串的定位操作,即查找子串在主串中出现的位置。本文主要讲解串的经典模式匹配算法—Brute-Force。

      1 基本思想

        串的模式匹配也称为子串的定位操作。设有主串S和子串T,如果在主串S中找到一个与子串T相等的子串,则返回串T的第一个字符在串S中的位置。其中S称为目标串,子串T又称为模式串。

        Brute-Force的基本思想是:从主串S=“S(0) S1 ...S(n-1)”的第pos个字符开始与子串T=“T(0) T1 ...T(n-1)”的第一个字符比较,如果相等则继续比较后一个字符;否则从主串的下一字符开始与子串T的第一个字符重新开始比较,以此类推。如果在主串S中存在与子串T相等的连续字符序列,则匹配成功,函数返回子串T中第一个字符在主串S中的位置;否则,函数返回-1。简单的说,就是对主串的每一个字符作为子串的开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做T的长度的小循环,直到匹配成功或全部遍历完成为止。

        假设我们要从主串S=“goodgoogle”中,找到T=“google”这个子串的位置。步骤如下:

    1. 主串S的第一位开始,S与T得前三个字母都匹配成功,但S得第四个字母是d而T的是g。第一位匹配失败。如图所示,竖直连线表示相等,弯折线表示不等。

    QQ截图20140220164409

    2. 主串S第二位开始,主串S首字母为o,模式串T的首字母为g,匹配失败,如图所示:

    QQ截图20140220164948

    3.主串S第三位开始,主串S首字母为o,模式串T的首字母为g,匹配失败,如图所示:

    QQ截图20140220170713

    4.主串S第四位开始,主串S首字母为d,模式串T的首字母为g,匹配失败,如图所示:

    QQ截图20140220170913

    5.主串S第五位开始,S与T,6个字母全匹配,匹配成功,如图所示:

    QQ截图20140220171315

    2 算法实现

        假设串采用顺序存储方式存储,并假设主串S和模式串T的长度存在S[0]和T[0]中,则Brute-Force匹配算法如下:

       1: /* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0 */
       2: /* T非空,1<=StrLength(S) 。*/
       3: int B_FIndex( String S , String T , int pos )
       4: {
       5:     int i = pos ;       //i用于主串S中当前位置下标,若pos不为1,则从pos位置开始匹配
       6:     int j = 1 ;         //j用于子串T中当前位置下标
       7:     while ( i<= S[0] && j <= T[0] )  //若i小于S长度且j小于T长度时循环
       8:     { 
       9:         if ( S[i] == T[j] )           //两字母相等时继续
      10:         {
      11:             ++i ;
      12:             ++j ;
      13:         }
      14:         else                        //指针退回重新开始匹配
      15:         { 
      16:             i = i - j + 2 ;         //i退回上次匹配首位的下一位
      17:             j = 1 ;                 //j退回子串T的首位
      18:         }
      19:     }
      20:     if ( j > T[0] )
      21:         return i - T[0] ;
      22:     else 
      23:         return 0 ;
      24: }
    
    

    3 算法分析

        Brute-Force匹配算法简单、易于理解,但是执行效率不高。在此算法中,即使主串与子串已有多个字符经过比较且相等,但只要有一个字符不相等,就需要将主串的比较位置退回。

        例如,假设主串S=“aaaaaaaaaaaaab”,子串T=“aaab”。其中n=14 ,m=4。每次比较子串的最后一个字符与主串中的字符不相等,所以均需将主串的指针退回,从主串的下一个字符开始与子串的第一个字符重新比较。在整个匹配过程中,主串的指针需要退回9次,匹配不成功的比较次数10*4,成功匹配的比较次数4次,总的比较次数为10*4+4=11*4 ,即( n–m+1)*m 。

        设主串的长度为n,子串的长度为m。Brute-Force匹配算法在最好的情况下,即主串的前m个字符刚好与子串相等,时间复杂度为O(m)。在最坏的情况下,Brute-Force匹配算法的时间复杂度为O(n*m)。

    转载于:https://www.cnblogs.com/hust-ghtao/p/3558298.html

    展开全文
  •   串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配,如果找到,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。...

      串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配,如果找到,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。t也称为模式。

    串的模式匹配有两种算法:
    • 简单的模式匹配算法
    • KMP算法

    简单的模式匹配算法:
      算法思想:首先将s1与t1进行比较,若不同,就将s2与t1进行比较,…,直到si和t1相同,再将它们之后的字符进行比较,若也相同,则如此继续往下比较,当si与tj不同时,则s返回到本趟开始字符的下一个字符,即si-j+2,t返回到t1,继续开始下一趟的比较,重复上述过程。若t中的字符全部比完,则说明本趟匹配成功,本趟的起始位置是i-j+1或i-t[0],否则,匹配失败。
      该算法比较简单,算法代码这里就不再给出。
    KMP算法
      算法思想:算法中引入一个next数组:
    next[j]={0,j=1Max1, next[j]=\left\{ \begin{aligned} 0,当j = 1时 \\ Max \\ 1,其他情况 \end{aligned} \right.
      其中:Max的取值为:
    Max={k1&lt;k&lt;jp1p2...pk1=pjk+1...pj1 Max=\left\{ \begin{aligned} k|1&lt;k&lt;j且&#x27;p_1p_2...p_{k-1}=&#x27;&#x27;p_{j-k+1}...p_{j-1}&#x27; \end{aligned} \right.
    例如:

    next[j]的计算过程如下:

    • j=1时,根据定义next[1]=0;
    • j=2时,由于不存在这样的正整数k使得1<k<2,所以属于其他情况,此时next[2]=1;
    • j=3时1<k<3,此时k只能取2,比较p1与p2(即pj-k+1或者说是pj-1),发现a!=b,所以属于其他情况,next[3]=1;
    • j=4时1<k<4,此时k可以取2、3两个:首先k取2,则比较p1与p3(即pj-k+1或者说是pj-1),发现相等,说明k可以取2;然后计算k取3时的情况,需要判断p1p2与p2p3(即pj-k+1pj-1),发现ab!=ba,k不可以取3;最后找出k的最大取值为2,所以next[4]=2
    • j=5时1<k<5,此时k可以取2、3、4三个 :首先k取2,则比较p1与p4(即pj-k+1或者说是pj-1),发现相等,说明k可以取2;然后计算k取3时的情况,需要判断p1p2与p3p4(即pj-k+1pj-1),发现ab!=aa,k不可以取3;然后计算k取4时的情况,需要判断p1p2p3与p2p3p4(即pj-k+1pj-k+2pj-1),发现aba!=baa,k不可以取4;最后找出k的最大取值为2,所以next[5]=2
    • j=6时1<k<6,此时k可以取2、3、4、5四个:首先k取2,则比较p1与p5,发现由于a!=b,说明k不可以取2;然后计算k取3时的情况,需要判断p1p2与p4p5,发现ab==ab,k可以取3;然后计算k取4时的情况,需要判断p1p2p3与p3p4p5,发现aba!=aab,k不可以取4;然后计算k取5时的情况,需要判断p1p2p3p4与p2p3p4p5,发现abaa!=baab,k不可以取5;最后找出k的最大取值为3,所以next[6]=3
    • j=7时,同理照此方法取k=2、3、4、5、6进行比较,最后计算出没有一个k值满足,所以属于其他情况,因而next[7]=1
    • j=8时,按照上述方式进行计算k=2、3、4、5、6、7比较后,发现只有k只能取2,因而next[8]=2。

    从而得出next数组中的值

    算法代码如下:

    #include "stdafx.h"
    #include <stdio.h>
    
    //查找满足条件的最大的k值,tr为模式串,l为当前比较的位置
    int Max_k(char t[],int l)
    {
    	int i = 0;
    	int max = 0;
    	int k = 0;
    	bool bIsEqual = true;
    	for(k = 2;k < l;k++)
    	{
    		bIsEqual = true;
    		for(i = 1;i <k;i++)
    		{
    			if(t[i] != t[l-k+i])
    				bIsEqual = false;//不满足'p1p2...p(i-1)==p(l-k+1)...p(l-1)'条件
    		}
    		if(bIsEqual)
    			max = k;
    	}
    	return max;
    }
    //计算模式串的next[j]数组
    void NextArr(int next[],int t_len,char t[])
    {
    	next[1] = 0;//netx[1]=0
    	next[2] = 1;//1<k<i,此时i = 2,为其他情况,所以next[2] = 1
    	int i = 3;
    	int max = 0;
    	for(i = 3;i < t_len;i++)
    	{
    		max = Max_k(t,i);
    		if(0 == max)
    			next[i] = 1;//其他情况
    		else
    			next[i] = max;
    	}
    }
    //找到匹配的主串开始位置
    //s:主串,t:子串,s_len:主串长度,t_len:子串长度,pos:从主串的pos位置处开始查找,next:不匹配时j的重新定位位置
    int KMP_Pos(char s[],char t[],int s_len,int t_len,int pos,int next[])
    {
    	int i = pos;
    	int j = 1;
    	while(i < s_len && j < t_len)
    	{
    		if(j == 0 || s[i] == t[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    	if(j >= t_len)
    		return i - t_len + 1;
    	else
    		return 0;
    }
    
    int main(int argc, char* argv[])
    {
    	char s[] = {'0','a','b','a','b','c','a','b','c','a','c','b','a','b'};//主串
    	int s_len = 14;
    	char t[] = {'0','a','b','c','a','c'};//模式串
    	int t_len = 6;
    	int next[6];
    	NextArr(next,t_len,t);
    	int pos = KMP_Pos(s,t,s_len,t_len,1,next);
    	printf("主串匹配模式串的第一个位置为:%d\n",pos);
    	return 0;
    }
    
    

    运行结果为:
    在这里插入图片描述
      KMP算法的难点就在于计算next数组,当计算出模式串的next的数组后,再去进行模式串匹配算法就比较简单了。

    展开全文
  • 串的模式匹配算法 一、基本概念 1、模式匹配(定位) 设有主串S和子串T(将S称为目标串,将T称为模式串),在主串S中,从位置start开始查找,如若在主串S中找到一个与子串T相等的子串,则返回T的第一个字符在主串...
  • title: 串的模式匹配算法之kmp tags: 数据结构与算法之美 author: 辰砂 1.引言 首先我们需要了解串的模式算法目的:确定主串中所含子串第一次出现的位置(定位);常见的算法种类: BF算法(又称古典的、经典...
  • 串的模式匹配算法(KMP算法,BF算法+算法详解+实现代码) 子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置,又被称为串的模式匹配 一、BF模式匹配算法 BF算法思想:Brute-Force算法又称蛮力匹配算法...
  • KMP算法重温——改进型串的模式匹配算法 1.暴力法求子串位置的定位函数。 暴力算法的思想是遍历主串中的字符,看是否和子串中的首字符一直,若相等,则继续比较主串中和子串匹配的字母的下一个字符,看是否与子串...
  • 算法的基本思想是:从主串S的第pos个字符起和模式的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较。依次类推,直至模式T中的每个字符依次和主串S中的一个连续的...
  • 文章目录一、BF算法原理设计思想:二、时间复杂度三、C++实现代码 一、BF算法原理 BF算法是一种蛮力算法,其实现过程没有任何技巧,就是简单...(2)当出现字符不匹配(失配)时,主串的比较位置重置为起始位置的...
  • 文章目录串的模式匹配子串定位基本算法(暴力搜索)改进的模式匹配算法:KMP1.算法思想2.next数组3.next数组值的手工求法4.计算next数组值的程序算法4. KMP模式匹配算法5. nextval数组 串的模式匹配 串的模式匹配与...
  • 串的模式匹配 模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串...
  • 本文主要讲述串的三种模式匹配算法(主串和模式串中字符都存放在下标1-length中)。 一、简单模式匹配算法 1.算法思想 (1)定义i和j两个指针,i指向主串,j指向模式串,i=j=1; (2)i指向主串最后一个元素的下一个...
  • KMP算法 串的模式匹配算法优秀总结

    千次阅读 2016-05-20 12:21:14
    这几天学习kmp算法,解决字符串的匹配问题,开始的时候都是用到BF算法,(BF(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的...
  • 串的模式匹配中,子串P称为模式,主串S称为目标。 示例: 目标S:"Beijing" 模式P:"jin" 匹配结果 = 3(匹配位置从0开始) 求子串位置的定位函数 Brute—Force 简称BF算法,亦称简单匹配算法。采用穷举的思想...
  • 一、对一个串中的某子串的定位操作称为 串的模式匹配; 二、模式串:待定位的子串 三、基本思想:从主串中的第一个位置起和模式串的第一个字符开始比较 如果相等,则继续比较后续字符; 如果不等,则从主串的第...
  • 串的第pos个位置,和模式的第1个位置开始比较,如果相等,则继续比较后续字符;若不等,则 i 指针跑到pos的下一个位置上,j 指针继续从第1个位置开始比较……直到找到对应的子串。 代码如下: int Index(SString ...
  • 【笔记】串的模式匹配算法

    千次阅读 2017-10-22 00:28:31
    一BF算法 BF算法思想 BF算法实现C语言 二KMP算法 KMP算法思想 next函数算法 KMP算法实现C语言 三模式匹配应用举例
  • 字符串的模式匹配 寻找字符串p在字符串t中首次出现的起始位置 字符串的顺序存储 typedef struct { char str[MAXSIZE]; int length; }seqstring; 朴素的模式匹配算法 基本思想:用p中的每一个字符去与t中的...
  • 一、Brute-Force模式匹配算法 public class BruteForce { /** * Brute-Force(暴风算法) * 算法思想: * 从目标s第一个字符起和模式t第一个字符进行比较,若相等,则继续逐个比较后续字符, *...
  •  先以主串S中第pos个字符为S子串的第一个字符,模式串T的长度作为S子串的长度,得到一个子串去与模式串T中的对应字符逐个比较,若子串与模式串相同,则返回S中子串的第一个字符位置,这就是模式串在主串S中的位置;...
  • Brute-Force算法的思想 1.BF(Brute-Force)算法 ...Brute-Force算法的基本思想是: ...1) 从目标s 第一个字符起和模式...2) 依此类推,直至t 中每个字符依次和s一个连续字符序列相等,则称模式匹配成功
  • 分为两种:一种为朴素的模式匹配算法(简称BF算法),改进的模式匹配算法(简称KMP算法)。 下面首先来介绍一下BF算法的中心思想: 这是一种带有回溯的匹配算法,简称BF算法。实现过程是从主S的第一个字符开始和...
  • 思想:从主串的第一个位置起和模式串的第一个字符进行匹配,如果相等则继续匹配,否则从主串的第二个字符开始逐一比较。以此类推,知道全部匹配完成。 如:str: ababc str1:abc 第一轮匹配匹配失败,下次从str...

空空如也

空空如也

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

串的模式匹配算法思想