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

    2013-11-25 08:31:59
    这里主要想讨论一下字符串的模式匹配,主要是KMP算法。 假设我们有一个字符串S,称之为原始串;另一个字符串T,称之为模式串;字符串匹配是指找出原始串S中是否含有模式串T,如果含有,则返回S中第一个匹配项的位置...

    0) 引论

    这里主要想讨论一下字符串的模式匹配,主要是KMP算法。

    假设我们有一个字符串S,称之为原始串;另一个字符串T,称之为模式串;字符串匹配是指找出原始串S中是否含有模式串T,如果含有,则返回S中第一个匹配项的位置;

    例如S=“abcabcabdef”;T=“abcabd”;那么我们可以得到S中含有模式串T,我们返回S中第一个匹配项的位置,即3。


    1) Brute-Force算法

    暴力算法,应该算是最朴素的算法了,大概小学生也能想出这个解决方法;BF算法的思想是:从S的第一个字符与T的第一个字符开始比较,如果相等,则进行下一个字符的比较,直到遇到不相等的项;这时我们把T的第一个字符与S的第二个字符相比较,重复上面的过程,知道找到匹配的项为止,或者返回一个值,显示没有匹配的项。

    对上面的例子:

    abcabcabdef

    abcabd;

    可知匹配不成立,所以要把T向右移一位,即

    abcabcabdef

        abcabd;

    还是不成立,继续右移一位

    abcabcabdef

            abcabd;

    还是不成立,继续右移一位

    abcabcabdef

                abcabd;

    这时我们得到了匹配,返回位置3。

    由此可见,BF算法就是一个类似于穷搜的算法,这个算法的时间复杂度为O(strlen(S)*strlen(T))。空间复杂度为O(1)

    代码实现:

    # include<stdio.h>
    #include<string.h>
    #include<windows.h>
    int BruteForce(char *S,char *T)
    {
    	unsigned int i=0,j=0;
    	int k=0;
    	while(i<strlen(S)&&j<strlen(T))
    	{
    		if(S[i+k]==T[j])
    		{
    			k++;
    			j++;
    		}
    		else
    		{
    			i++;
    			j=0;
    			k=0;
    		}
    		if(S[i+strlen(T)-1]==T[strlen(T)-1])
    		{
    			return i;
    			break;
    		}
    	}
    
    }
    void main()
    {
    	char *S,*T;
    	S = "abcdabcabdef";
    	T = "abcabd";
    	int BF;
    	BF = BruteForce(S,T);
    	printf("%d\n",BF);
    	system("pause");
    }

    2) KMP算法

    上面介绍的Brute-Force算法很简单也相当好理解,但是作为一个受过多年高等教育的人来说,用上面的方法简直是一种侮辱,因此我们需要更加复杂,更有挑战的算法(纯属玩笑话)。其实最主要的原因是上面的算法耗时,做了一些无用的功。每次把模式串向右移动一步并不够,例如上面的例子我们可以很容易的得到应该把T向右移动3步比较合适,那么怎么让计算机能够做到的,那么我们就需要KMP算法。同时我们也可以看到上面的算法没有利用T中已经匹配了的字符的一些信息。

    KMP算法由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的。KMP算法的与BF算法的最大的不同就在于“失配”的处理上,BF算法当遇到失配时,做法是把模式串向右移动一位;而KMP算法则是向右移动更多的位,这个由一个next数组控制,已达到加速的目的。

    对上面的例子:

    abcabcabdef

    abcabd;

    我们可以得到在位置5处,发生了失配,也就是S[5]!=T[5]。那么对于KMP算法,我们需要将T向右移位,也就是说要另S[5]==T[next[5]];更通用的表述是当S[i]!=T[j]时,令j=next[j],使S[i]==T[next[j]],也就是说相当于将T向右移动了j-next[j]>=1位。因此KMP算法的核心就是next数组。next数组只与模式串T的本身性质有关,而与原始串S无关。

    下面我们来看next数组怎样求:


    KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++j++,继续匹配下一个字符;如果匹配失败,即S[i] != T[j],需要保持i不变,并且让j = next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1(移动的实际位数j - next[j]  >=1)。

    因此要应用KMP算法,我们首先可以利用模式串T来得到相应的next数组。

    a) next[0]=-1: 任何串的首字符的next值为-1;

    b) next[j]=-1: 模式串T中下标为j的字符,如果与首字符相同,且j的前面的1—k个字符与开头的1—k个字符不等(或者相等但T[k]==T[j])(1k<j)。

    c) next[j]=k:  模式串T中下标为j的字符,如果j的前面k字符与开头的k个字符相等,且T[j] != T[k] 1k<j

    d) next[j]=0:  除了上面的情况外其他的情况。

    next数组值的意义

    设在字符串S中查找模式串T,若S[m]!=T[n],那么,取T[n]的模式函数值next[n],

    a) next[n]=  -1 表示S[m]和T[0]间接比较过了,不相等,下一次比较 S[m+1]和T[0]。

    b) next[n]=0 表示比较过程中产生了不相等,下一次比较 S[m] 和T[0]。

    c) next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了,下一次比较S[m]和T[k]是否相等。

    int *Next(char *T,int *next)
    {
    	int j = 0, k = -1;
    	next[0] = -1;
    	while ( T[j] != '\0' )
    	{
    		 if (k == -1 || T[j] == T[k])
    			{
    				++j; ++k;
    				if (T[j]!=T[k])
    					next[j] = k;
    				else
    					next[j] = next[k];
    			 }
    		  else
    			  k = next[k];
    	}
    }


    展开全文
  • 关于字符串的模式匹配问题,在绝大多数讲数据结构的书中都会提到,关于字符串的模式匹配算法,一共有两个,下面就来一一介绍。 第一种,朴素模式匹配(时间复杂度为O(mn)) 之所以把这种算法称作朴素模式匹配,我...

    针对字符串的模式匹配问题,解决的算法有挺多的,下面就把我所知道的一一介绍吧。

    第一种,朴素模式匹配(时间复杂度为O(mn))

    之所以把这种算法称作朴素模式匹配,我想大概是因为这个算法可以看做是在通过遍历,从而完成匹配,这种方式应该是比较朴素的。(个人看法)

    举例来说吧。

    主串s = “abcdabcde”,子串t = “abcde”

    (1)从主串第一个字符开始,和子串中的字符进行逐一比较,可以发现前四个字符都匹配成功,而第四个没有匹配成功;

    (2)主串的开始下标+1,然后再继续跟子串匹配(子串从0下标开始);



    (3)没有匹配成功,就重复第二步,直到全部匹配成功,或者说主串s已到达末尾。




    实现代码:

    		private static int simple(String s, String t) {
    		int i = 0;// 记录主串下标
    		int j = 0;// 记录子串下标
    
    
    		while (i < s.length() && j < t.length()) {
    
    
    			if (s.charAt(i) == t.charAt(j)) {
    
    
    				// 当前位置字符匹配成功
    				i++;// 主串下标+1
    				j++;// 子串下标+1
    
    
    			} else {
    
    
    				// 当前位置字符匹配不成功
    				i = i - j + 1;//i-j:主串回到匹配初始位置,+1:主串下标+1
    				j = 0;// 子串下标置零
    
    
    			}
    		}
    		// 匹配成功,返回模式串p在文本串s中的位置,否则返回-1
    		if (j == t.length())
    			return i - j;
    		else
    			return -1;
    	}

    第二种,快速模式匹配(时间复杂度为O(n))

    快速模式匹配算法,实现了保持主串的检索位置不懂,而移动子串的检索位置,省去了一些不必要的操作,提高了效率。而要想确定子串的检索位置应该怎么移动,就需要了解几个概念:前缀、后缀。举个例子来说吧,给定字符串“ABCDABD”,

    也就是说,原模式串子串对应的各个前缀后缀的公共元素的最大长度表为:


    这个表其实就是next数组的前身,把表中数据都往后移一位,并在首位填上-1,即:


    其实整个KMP算法的实现,我觉得关键就在于如何获得next数组,next数组其实就是查找模式串中每一位前面的子串的前后缀有多少位匹配,从而决定在失配时子串检索位置应该回退到哪个位置,那接下来就来推敲一下,如何获得next数组吧。

    由于我个人的表达能力有限,建议参考http://www.cnblogs.com/tangzhengyue/p/4315393.html,讲的很清楚,通俗易懂。

    代码实现:

    public static int[] getNext(String t) {
    
    		int[] next = new int[t.length()];
    
    		next[0] = -1;
    
    		int j = 0;
    
    		int k = -1;
    
    		while (j < t.length() - 1) {
    			if (k == -1 || t.charAt(j) == t.charAt(k)) {
    
    				next[++j] = ++k;
    			} else {
    
    				k = next[k];
    			}
    		}
    
    		return next;
    	}
    
    	public static int KMP(String s, String t) {
    
    		int i = 0;
    		int j = 0;
    
    		int[] next = getNext(t);
    
    		while (i < s.length() && j < t.length()) {
    
    			if (j == -1 || s.charAt(i) == t.charAt(j)) { // 当j为-1时,要移动的是i,当然j也要归0
    
    				i++;
    				j++;
    			} else {
    				// i不需要回溯了
    
    				j = next[j]; // j回到指定位置
    			}
    		}
    		
    		if (j == t.length()) {
    
    			return i - j;
    
    		} else {
    
    			return -1;
    
    		}
    	}
    第三种,Boyer-Moore 算法,简称 BM 算法。

    BM 算法定义了两个规则:

    • 坏字符规则:当文本串中的某个字符跟模式串的某个字符不匹配时,我们称文本串中的这个失配字符为坏字符,此时模式串需要向右移动,移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外,如果"坏字符"不包含在模式串之中,则最右出现位置为 -1。
    • 好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为 -1。
    第四种,Sunday算法。
    Sunday 算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
    • 如果该字符没有在模式串中出现则直接跳过,即移动位数 = 匹配串长度 + 1;
    • 否则,其移动位数 = 模式串中最右端的该字符到末尾的距离 +1。

    展开全文
  • Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过... 要理解Sunday算法,建议先阅读《字符串的模式匹配: BF算法》、《字符串的模式匹配:KMP

      Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP,BM的实现容易太多。
      要理解Sunday算法,建议先阅读《字符串的模式匹配: BF算法》《字符串的模式匹配:KMP算法》 《字符串的模式匹配:BM算法 》
      时间复杂度:最差情况O(MN),最好情况O(N)

    算法思想:

      在匹配过程中,先从左到右逐个字符比较,当模式串发现不匹配时,跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。
      模式串向后位移:字符串和模式串同时移动的长度 + 模式串的长度 - 该字符在模式串中出现的第一个位置(从右向左寻找模式串,如果寻找不到则为-1)。
      开始的时候,让字符串”T”的第一个字符T[0]和模式串”P”的第一个字符P[0]匹配,如果不匹配。以字符串出现在模式串后面的位置n,取T[n]字符,找到该字符在模式串字符的的位置k,并将模式串p[k]字符与T[n]对齐,即模式串向后位移n-k; 若在模式串中找不到T[n]字符,则将模式串p[0]与字符串T[n]对齐,模式串向后以模式串长度位移。位移后再比对P[0]和T[N], 按照上述过程依此匹配。
      下面还是看一下实际的匹配过程,道理可能讲的是不够清晰。

    匹配过程:

    假设有字符串和模式串如下:
    字符串T: “Lessons tearned en software te”
    模式串P: “software”
    模式串P的长度为8。字符串T的长度为30。

    1、首先字符串T和模式串P首字符对齐。如下:

    Lessons tearned en software te
    software

    2、然后T[0]和P[0]字符匹配,也就是”L”和”s”, 这个时候不匹配;根据Sunday算法要求,以字符串出现在模式串后面的位置n,取T[n]字符,找到T[n]即T[8]字符”t”位于模式串P中从后向前查找出现的第一个位置,即模式串的P[3]。模式串向后位移:字符串和模式串同时移动的长度 + 模式串的长度 - 该字符在模式串中出现的第一个位置。 模式串移动位数 = 0 + 8 - 3 = 5位, 位移5位后T[8]与P[3]对齐后得到如下结果:

    Lessons tearned en software te
         software

    3、比对T[5]和P[0],也就是”n”和”s”, 这个时候不匹配,再次寻找字符串中在模式串后面的那个字符在模式串中出现的位置。也就是字符串的tearned 中的”e”,并且寻找”e”在模式串出现的位置,也就是模式串的P[7]位置。此时模式串位移 = 0 + 8 - 7 = 1位。位移后得到结果:

    Lessons tearned en software te
          software

    4、此时,对比T[6]和P[0],也就是”s”和”s”, 发现字符匹配。那么字符串和模式串同时向后移1位。 对比T[6+1]和P[0+1], 也就是字符串的” “和模式串的”o”,发现 再次不匹配。找到字符串在模式串后移1位T[6+1+8]的字符” “, 寻找字符”d”在模式串的位置,发现模式串中不存在d,也就是说。 模式串移动位数 = 1 + 8 - (-1) = 10, 移动结果如下:

    Lessons tearned en software te
                    software

    5、依此类推,直到找到匹配的位置,或者到达字符串的末尾 。

    再假设有字符串和模式串如下:
    字符串T: “Lessonsotearned en software te”
    模式串P: “software”
    模式串T的长度为8。字符串T的长度为30。
    其匹配过程,第1、2、3步与上诉例子的1、2、3不一样,运行后位移如下:

    Lessonsotearned en software te
          software

    那么如上对齐后,匹配字符串T[6]与模式串P[0], 也就是”s”和”s”, 匹配一致。那么字符串T和模式串P后移1位,匹配字符串T[6+1]与模式串P[0+1],也就是”o”和”o”, 匹配一致。那么字符串T和模式串P再次后移1位,匹配字符串T[6+1+1]与模式串P[0+1+1],也就是”t”和”f”不一致。所以模式串移动位数 = 2 + 8 - 7 = 3, 得到结果如下:

    Lessonsotearned en software te
             software

    直到找到匹配的位置,或者到达字符串的末尾 。

    具体实现(java):

        /// <summary>
        /// 通过Sunday查找算法,查找text串中pattern字串的第一次出现的位置,没查找到返回-1
        /// </summary>
        /// <param name="text">目标(源)串</param>
        /// <param name="pattern">匹配串</param>
        /// <returns>int,返回第一次出现的索引.返回-1表示没有找到.</returns>
        public static int sundaySearch(char[] text, char[] pattern){
            int i = 0, j = 0, k;/*分别记录text索引,pattern索引还有,串匹配计数时索引*/
            int tl, pl;/*分别记录字符串text和pattern的长度*/
            int pe;/*分别记录text匹配pattern最后的索引的下一个索引*/
            int rev=-1;/*记录返回的索引值,否则无法返回*/
    
            /*非法情况,直接返回-1*/
            if ((text == null) || (pattern == null) || (tl = text.length) < (pl = pattern.length))
                return -1;
    
            while (i < tl && j < pl) {
                /* 匹配正确就仅继续匹配 */
                if (text[i] == pattern[j]) {
                    ++i;
                    ++j;
                    continue;
                }
                pe = i + pl;
                /* 匹配失败,移动i和j索引值,为下一次匹配做准备 */
                if (pe >= tl) /* 当下一次的位置已经超过text的长度时,返回-1表示没有找到 */
                    return -1;
                for (k = pl - 1; k >= 0 && text[pe] != pattern[k]; --k)
                    ;
                i += (pl - k);// (pl - k)表示i需要移动的步长
                rev = i;// 记录当前的索引
                j = 0;/* j重新开始 */
                // System.out.println("总移动位数:" + rev);
            }
            return i <= tl ? rev : -1;
        } 
    展开全文
  • 字符串的模式匹配 寻找字符串p在字符串t中首次出现的起始位置 字符串的顺序存储 typedef struct { char str[MAXSIZE]; int length; }seqstring; 朴素的模式匹配算法 基本思想:用p中的每一个字符去与t中的...

    字符串的模式匹配

    寻找字符串p在字符串t中首次出现的起始位置

    字符串的顺序存储

    typedef struct
    {
    	char str[MAXSIZE];
    	int length;
    }seqstring;

    朴素的模式匹配算法

    基本思想:用p中的每一个字符去与t中的字符一一比较。

    模式p 正文 t

    如果匹配成功,则返回p在t中首次出现的起始位置

    如果匹配不成功则返回-1

    最坏情况比较次数可达:(n-m+1)*m次

    int index(seqstring p,seqstring t)
    {
    	int i,j,flag;
    	i=0;flag=0;
    	while((i<=t.length-p.length) && (!flag))
    	{
    		j=0;flag=1;
    		while(j<p.length && flag)
    		{
    			if(p.str[j]==t.str[i+j])
    			{
    				j++;
    			}
    			else
    			{
    				flag=0;
    			}
    		}
    		++i;
    	}
    	if(flag)
    	{
    		return (i-1);
    	}
    	else
    	{	
    		return -1;
    	}
    }

    或者另一种朴素模式匹配算法

    int index(seqstring t,seqstring p)
    {
    	//t是文本串,p是模式串
    	int i=0,j=0;
    	while(i<t.length && j<p.length)
    	{
    		if(p.str[j]==t.str[i])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+1;//需要琢磨
    			j=0;
    		}
    	}
    	if(j==p.length)
    	{
    		return (i-j);
    	}
    	else
    	{
    		return -1;
    	}
    }

    在学习KMP算法之前:

    真前缀:除了自身以外,一个字符串的全部头部组合

    真后缀:除了自身以外,一个字符串的全部尾部组合

    (注意区分 前缀 和 真前缀)

    KMP算法的流程:

    假设现在文本串S匹配到i位置,模式串P匹配到j位置

    如果j==-1 或者 当前字符匹配成功,则i++,j++,继续匹配下一个字符

    如果匹配失败,那么模式串向右移动的位数:失配字符所在位置-失配字符对应的next值。

            这时:j=6,next[j]=2,所以向右移动 j-next[j]=6-2=4个位置。                                                                          

    或者基于《最大长度表》:以匹配字符数-失配字符的上一位字符所对应的最大长度值

            这时:以匹配字符为6,失配字符的上一位字符所对应的最大长度值=2,所以向右移动 6-2=4个位置。

    int KMP_search(seqstring s,seqstring p,int next[])//文本串S,模式串P
    {
    	int i=0,j=0;
    	while(i<s.length && j<p.length)
    	{
    		if(j==-1 || s.str[i]==p.str[j])
    		{
    			//如果j=-1或者当前字符匹配成功,即s[i]==p[j]
    			i++;
    			j++;
    		}
    		else
    		{
    			//当匹配失败时,模式串向右移动的位数为:失配字符所在位置-失配字符对应的next值
    			j=next[j];
    		}
    	}
    	if(j==p.length)
    	{
    		return (i-j);
    	}
    	else
    	{
    		return -1;
    	}
    }

    在KMP算法中有一个next数组相当关键

    所以首要的是求出next数组的各个值

    next数组的求解:

    求解基于“真前缀”和“真后缀”,next[i]最长相同的前后缀的长度

    根据《最大长度表》求解next[ ]数组

    例:对于字符串ABCDABD

    《最大长度表》

    字符 A B C D A B D
    最大前后缀公共元素长度 0 0 0 0 1 2 0

    next数组相当于最大长度表向后移一位,然后初始值赋值为-1。

    可以不通过这个最大长度表直接计算next数组的值,即这个字符之前的字符串有多大长度的相同的前后缀(真前后缀)。

    《next[] 数组》

    i 0 1 2 3 4 5 6 7
    模式串 A B C D A B D \0
    next[i] -1 0 0 0 0 1 2 0

    i=0时,对于模式串的首位,我们统一为next[0]=-1

    i=1时,前面的字符为A,其最长相同真前后缀长度为0,next[1]=0

    i=2时,前面的字符为AB,其最长相同真前后缀长度为0,next[2]=0

    i=3时,前面的字符为ABC,其最长相同真前后缀长度为0,next[3]=0

    i=4时,前面的字符为ABCD,其最长相同真前后缀长度为0,next[4]=0

    i=5时,前面的字符为ABCDA,其最长相同真前后缀长度为1,next[5]=1

    i=6时,前面的字符为ABCDAB,其最长相同真前后缀长度为2,next[6]=2

    i=7时,前面的字符为ABCDABD,其最长相同真前后缀长度为0,next[7]=0

     

    下面需要思考的是:如果知道了next[ j ],怎么得到next [ j+1]呢?

    next[ j ]=k,代表 j 之前的模式子串中,有长度为 k 的相同的前缀和后缀。

    有了这个next[]数组,在KMP匹配中,当模式串 j 处失配时,模式串向右移动 j-next[j] 位。

    1、对于模式串来说,如果p[ j ]==p[ k ],那么next[j+1]=next[ j ]+1 = k+1(p[ k ]是前缀,p[ j ]是后缀)

    这里 k=2,j=6,p[k]=p[j],所以next[ j+1 ] = next[ j ]+1 = k+1 = 2+1 = 3。

    2、如果p[ j ] != p[ k ],那么就说明 “p0p1...pk-1pk” 不等于 “pj-k...pj-1pj”。

    这里j=2,k=6,ABC!=ABD,那么在字符E前没有长度为k+1的相同的前后缀,需要去找一个长度更短一些的前后缀。

    思路:与上面的模式串与文本串匹配类似(与KMP思路类似),当p0p1p2...pj跟主串s0s1...si匹配时,如果在模式串j处失配,则模式串需要向右移动 j-next[j] 位,相当于 j = next [ j ]。

    而现在是前缀与后缀匹配,"p0p1..pk-1pk"和"pj-k...pj-1pj"匹配时,发现在pk处匹配失败,若能在前缀"p0...pk-1pk"中不断递归前缀索引k=next[k],找到一个字符pk’==pj,且满足" p0pk'-1pk'  "==" pj-k'pj-1pj ",则最大相同的前后缀长度为k'+1,从而next[j+1]=k'+1=next[k']+1。否则继续递归k'=next[k'],直到next[k']=0。

    void getnext(seqstring p,int next[])
    {
    	int i=0;
    	int j=-1;
    	next[0]=-1;
    	while(i<p.length)
    	{
    		if(j==-1 || p.str[j]==p.str[i])
    		{
    			++i;
    			++j;
    			next[i]=j;
    		}
    		else
    		{
    			j=next[j];
    		}
    	}
    	printf("未优化:\n");
    	for(i=0;i<p.length;i++)
    	{
    		printf("%5d",next[i]);
    	}
    	printf("\n");
    	return ;
    }

    next数组的优化

    应用上面的KMP算法,以及next[]数组的求解算法得到next数组中的各个值。

    在下面这个例子中,因为 ‘c’和‘b’不匹配,所以模式串右移j-next[j]=3-1=2位。右移了两位后,又是b与c的匹配,显然也是不匹配的。那么出现这种情况的原因是:p[j]=p[ next[j] ]。因为p[j]!=p[i],如果 p[ j ]==p[ next[ j ] ] ,那么必然会导致下一次匹配的失败,所以对求解next数组的函数进行进一步的优化。

    void getnext(seqstring p,int next[])
    {
    	int i=0;
    	int j=-1;
    	next[0]=-1;
    	while(i<p.length)
    	{
    		//p[j]表示前缀,p[i]表示后缀
    		if(j==-1 || p.str[j]==p.str[i])
    		{
    			++i;
    			++j;
    			//在前j+1个字符都匹配了以后,i+1,j+1,这时如果满足下面的if条件,则next[i]就是该字符之间的相同前后缀的长度
    			if(p.str[j]!=p.str[i])
    			{
    				//如果两个不相同,就直接存储前面的子串的(以匹配的)长度
    				next[i]=j;
    			}
    			else
    			{
    				//因为出现两个字符一样的情况,所以在使用KMP算法时,为了避免出现p[j]==p[next[j]]使算法效率变低,
    				//所以当出现时需要递归,j=next[j]=next[next[j]].
    				next[i]=next[j];
    			}
    		}
    		else
    		{
    			j=next[j];
    		}
    	}
    	printf("优化后:\n");
    	for(i=0;i<p.length;i++)
    	{
    		printf("%5d",next[i]);
    	}
    	printf("\n");
    	return ;
    }

    只要出现了p[ next[ j ] ]=p[ j ]的情况,则把next[ j ]再次递归。例如在求模式串abab的next数组时,对于未优化的next数组,第二个a对应的值是0,相当于第二个a失配时,下一步匹配模式串会用p[ 0 ]处的a再次与文本串匹配,必然是失配的。所以再求第二个a的next值时,需要再次递归next[ 2 ]=next[ next[ 2 ] ]=next[0]=-1。此后,根据优化的新的next的值可知,第二个a失配时,执行" j==-1 || p.str[j]==p.str[i] ,++i,++j,继续匹配下一个字符 ",同理,对应的b的next的值为0。(可以自己手动推导,或者单步调试)。

    对于优化后的next数组可以发现:如果模式串的后缀和前缀一样,例如abcdabcd,他们的前缀后缀都是abcd,其优化后的next数组是-1 0 0 0 -1 0 0 0,其前后缀的next值都是-1 0 0 0。

    KMP算法的时间复杂度

    回顾KMP算法的流程:

    假设现在文本串S匹配到 i 的位置,模式串P匹配到 j 的位置

    (1)如果j==-1 或者 S[ i ]==p[ j ],就 i++,j++,继续匹配下一个字符

    (2)如果 j != -1 && 当前的字符匹配失配,i不变(即 i 不回溯),j = next [ j ],模式串向右移动了 j-next[ j ]位。

    整个算法最坏的情况是:当模式串的首字符位于i-j的位置时才匹配成功

    如果文本穿的长度为n,模式串的长度为m,匹配过程的时间复杂度是O(n),求解next数组是O(m),KMP算法的复杂度是O(m+n)。

     

    有错的话,请大家及时指正!!!

    参考文献:

    1、 从头到尾彻底理解KMP(2014年8月22日版)

    2、从头到尾彻底理解KMP(2014年7月版)

    3、《数据结构(C语言版)》,李云清 杨庆红 揭安全编著

    4、KMP算法(1):如何理解KMP

    展开全文
  • 字符串的模式匹配:BM算法

    千次阅读 2017-03-19 15:38:03
    完成字符串匹配的算法,其在绝大多数场合的性能表现,比KMP算法还要出色,下面我们就来详细了解一下这一出色的单模式匹配算法,在此之前推荐读者读一下我的另一篇文章《字符串的模式匹配:KMP算法》,对于透彻理解BM...
  • 数据结构之字符串的模式匹配

    千次阅读 2015-08-25 21:49:40
    字符串的模式匹配问题: 一共有两种算法, 1.朴素模式匹配算法。 举例而言(寻找从S=”goodgoogle”中找到V=”google”这个子串):我们一般需要以下的步骤 (1).从主串的第一个字符开始,S与V中的字符逐一比较...
  • 字符串的模式匹配(精准匹配)

    千次阅读 2018-04-06 11:39:41
    朴素的模式匹配直接贴代码2.1字符串的的特征向量例如在目标(target)字符串t中:abcabcabcc中寻找模式(pattern)字符串p: abcabcc可见t6与p6不匹配如果用朴素的匹配思想只需要将模式串一次向右移动一位即可此时t3-t9与...
  • 数据结构面试之十四——字符串的模式匹配 题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。 十四、字符串的模式匹配 1.  模式匹配定义...
  • 两种方法主要的区别在于,调用方法的对象和传递的参数,正则表达式的方法调用方法的对象是正则表达式,传输的参数是字符串,而字符串的模式匹配调用方法的对象是字符串,传递的参数是正则表达式。RegExp对象的方法:...
  • 实现串的BF模式匹配算法,统计在匹配过程中总的字符比较次数,当主串剩余部分不足子串长度时,停止比较。 Input 输入包含两行,第一行为主串s,第二行为子串t。 Output 输出包含两行,第一行为子串在主串中的位置,...
  • String 类型定义了几个用于在字符串匹配模式的方法。第一个方法就是 match() ,在字符串上调用这个方法,本质上与调用 RegExp exec() 方法相同。 match() 方法只接受一个参数,要么是一个正则表达式,要么是一...
  • KMP算法是模式匹配的一种改进的算法,所谓的模式匹配也就是对于两个字符串主串S和模式串T。从主串的S的pos个字符起和模式串中的第一个字符进行比较,如果相等,则继续比较后面的字符,否则从主串的下一个字符重新和...
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • 字符串的模式匹配: BF算法

    千次阅读 2017-03-17 15:10:15
    暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个...
  • 字符串的模式匹配:KMP算法

    千次阅读 2017-03-17 19:14:29
    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
  • 1、朴素的模式匹配算法/*返回子串T在主S中第pos个字符之后的位置。若不存在,则函数返回值为0。*/ /*T非空,1≤pos≤StrLength(S)。*/ int Index(String S, String T, int pos) { int i = pos; /*i用于主S中...
  • 蛮力法:设计算法求解字符串的模式匹配问题,并编程实现。
  • 字符串的模式匹配(KMP)算法

    千次阅读 2018-09-10 09:40:51
    给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。 Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin ...
  • 分为两种:一种为朴素的模式匹配算法(简称BF算法),改进的模式匹配算法(简称KMP算法)。 下面首先来介绍一下BF算法的中心思想: 这是一种带有回溯的匹配算法,简称BF算法。实现过程是从主S的第一个字符开始和...
  • 朴素的模式匹配算法 一个例子: 从主 S = "goodjob"中,找到子串 T = "job"的位置。我们通常需要下面的步骤。 1. 将子串"job"与主S从第一位对应匹配。即判断 whether 'g' == 'j'; 2. 判断结果为否,继续匹配 ...
  • Java数据结构之 字符串的模式匹配

    千次阅读 2018-05-13 16:56:31
    BF算法BF算法又称暴力匹配算法,比较方法:BF算法思想就是将主S第一个字符与子串T第一个字符进行匹配,若相等,则继续比较S第二个字符和 T第二个字符;若不相等,则比较S第二个字符和T第一个字符,...
  • 算法把模式P和文本T开头字符对齐,从模式的最后一个字符开始比较,如果尝试比较失败了,它把模式向后移。每次尝试过程中比较是从右到左。 Horspool 算法是一种基于后缀匹配的方法,是一种“跳跃式”匹配算法,...
  • 字符串的模式匹配:RK算法

    千次阅读 2017-03-20 15:00:20
    RK算法是由Rabin和Karp共同提出一个算法。 ... RK算法也可以进行多模式匹配,在论文查重等实际应用中一般都是使用此算法。  时间复杂度:O(MN)(实际应用中往往较快,期望时间为O(M+N))R
  • 字符串的模式匹配--BF算法&KMP算法

    千次阅读 2018-04-05 13:58:59
    BF算法是基于主指针回溯,重新与子串进行逐字符进行比较,主为S什么要进行回溯呢,原因在于模式P中存在相同的字符或者说由字符)存在重复(模式的部分匹配性质),设想如果模式P中字符各不相同,主就S...
  • #include<stdio.h> #include<string.h> void main() { char a[30],b[10]; scanf("%s",a); scanf("%s",b); int i,j,len_a,len_b,flag; len_a=strlen(a); len_b=strlen(b);... int...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,512
精华内容 11,004
关键字:

字符串的模式匹配