【数据结构】图解串的朴素模式匹配（C语言）

ゞ浴缸里的玫瑰 2023-02-16 06:47 6阅读 0赞

模式匹配：子串定位运算，在主串中找出子串出现的位置。

假设我们要从下面的主串S=“goodgoogle”中，找到T=“google”这个子串的位置。我们通常需要下面的步骤。

1、主串S第一位开始，S与T前三个字母匹配成功，但是S第四个字母是d而T的是g。第一位匹配失败。下图所示，其中竖直连线表示相等，闪电状弯折线表示不相等。  
![在这里插入图片描述][20200609102122902.png]  
2、主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败。  
![在这里插入图片描述][20200609102435620.png]  
3、主串S从第三位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败。  
![在这里插入图片描述][20200609114040270.png]  
4、主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败。  
![在这里插入图片描述][20200609114245921.png]  
5、主串S第五位开始，S与T，6个字母全匹配，匹配成功。  
![在这里插入图片描述][20200609114819918.png]  
简单的说，就是对主串的每一个字符作为子串开头，要与匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止。

//返回子串T在主串S中第pos个字符之后的位置。若不存在，返回0
    //T非空，1<=pos <=StrLength(S)
    int Index(Sitnrg S,String T,int pos)
    {
        
    	/*
    	i用于主串S中当前下标位置，若pos不为1，则从pos位置开始匹配
    	*/
    	int i = pos;
    	int j = 1; //j用于子串T中当前位置下标值
    
    	while(i <= S[0] && j <= T[0]) //i小于长度且j小于T的长度时循环
    	{
        
    		if(S[i] == T[i])  //字母相等则继续
    		{
        
    			++i;
    			++j;
    		}
    		else
    		{
        
    			i = i - j+ 2; //退回到上次匹配首位的下一位
    			j = 1;       //j退回到子串T的首位
    		}
    	}
    	if(j > T[0])
    		return i - T[0];
    	else
    		return 0;
    }

分析一下，最好的情况就是一开始就匹配成功，时间复杂发为O(1),最坏的情况就是每次匹配不成功的匹配都发生在串T的最后一个字符。

[20200609102122902.png]: https://img-blog.csdnimg.cn/20200609102122902.png
[20200609102435620.png]: https://img-blog.csdnimg.cn/20200609102435620.png?
[20200609114040270.png]: https://img-blog.csdnimg.cn/20200609114040270.png
[20200609114245921.png]: https://img-blog.csdnimg.cn/20200609114245921.png
[20200609114819918.png]: https://img-blog.csdnimg.cn/20200609114819918.png