首页 > 编程语言 >字符串匹配之Sunday算法

字符串匹配之Sunday算法

时间:2022-10-03 23:55:22浏览次数:62  
标签:匹配 int pattern 算法 模式 next Sunday 字符串 对齐

简介

Sunday算法是一种字符串匹配算法,相比于KMP算法,它比较简单易学。

在有些时候,比如字符串很长的时候,它是比KMP要高效的。

核心思想

  1. 从前往后匹配,匹配失败时关注主串中参与匹配的最末位字符的下一位。

  2. 该字符没有在模式串中出现,则直接跳过,且模式串移动位数 = 模式串长度 + 1。

  3. 否则,移动位数 = 模式串长度 - 该字符在模式串最右出现出现的位置。


这三步说明了具体的执行,感觉很抽象。但综合起来就是:

  • 匹配时从前向后匹配。
  • 匹配失败时,重新对齐模式串与主串。

所以现在的问题是,这个重新对齐是怎么对齐呢?

举个栗子

  • 设主串为 eurusdoveyesido
  • 设模式为 esid

  1. 正常匹配,在第2位发现不匹配,于是看主串中参与匹配的最末位字符的下一位,也就是ss也在模式串出现过,那么对齐


  1. 对齐后,继续正常匹配,发现第1位就不同,匹配失败。同样,看v,发现v没在模式串出现过,那么模式串就与v后面的e对齐


  1. 同样,匹配失败。对齐i


  1. 终于,匹配成功!

代码实现

_next数组

是的,Sunday算法也有next数组需要预处理。

next数组存储的是:模式串不同字符最右边的下标。

所以,对于上面例子的模式串 esid

  • \(next[d] = 3\)
  • \(next[i] = 2\)
  • \(next[s] = 1\)
  • \(next[e] = 0\)

而对于英文字符,它们都在ASCII里,总计256个,所以我们开一个256大小的数组

int _next[256];

void getnext(char pattern[])
{
	int len = strlen(pattern);
	int i;
	for(i = 0;i < 256; i ++)//初始化为 -1
	{
		_next[i] = -1;
	}
	int cnt = 0;
	for(i = len - 1;i >= 0;i --)
	{
		if(_next[i] == -1)
		{
			_next[(int)pattern[i]] = i;
			cnt ++;
			if(cnt == 256)//256满了就退出
			{
				break;
			}
		}
	}
}

这样的预处理,正是以空间换取时间

匹配过程

匹配的代码按思想写就好,值得一提的是:

因为模式串中没有出现的字符的next值为-1,所以正好,当要对齐的时候,模式串多向后移动了一位(减 负 1 -> 加 1)。

int SundaySearch(char pattern[],char dest[])
{
	getnext(pattern);
	int i, j, k;
	int lenp = strlen(pattern),lend = strlen(dest);
	for(i = 0;i < lend;)
	{
		j = i;
		for(k = 0;k < lenp && j < lend; k ++)//匹配的过程
		{
			if(dest[j] == pattern[k])
			{
				j ++;
			}else
			{
				break;
			}
		}
		if(k == lenp)//匹配成功,返回首字符下标
		{
			return i;
		}else
		{
			if(i + lenp < lend)//注意越界
			{
				i += lenp - _next[(int)dest[i + lenp]];
			}
			else
			{
				return -1;
			}
		}
	}
	return -1;
}

标签:匹配,int,pattern,算法,模式,next,Sunday,字符串,对齐
From: https://www.cnblogs.com/Az1r/p/16751593.html

相关文章

  • Java手写实现链表队列和数组队列【数据结构与算法】
    packagealgorithm;/**@authorAdministrator@date2022-09-1317:50*/publicclassQueueLinked{privatestaticclassNode{Eitem;Nodenext;publicNode(Eitem,N......
  • Java手写实现栈【数据结构与算法】
    packagealgorithm;importjava.util.Arrays;importjava.util.Iterator;/**@authorAdministrator@date2022-09-1216:38数组栈*/publicclassMyArrayStack{//定义......
  • 学习笔记:python字符串的处理方法
    python学习字符串处理方法1.str.lower()和str.upper()实现全大写和全小写。2.str.split()能够使字符串以一种格式分割开,并返回一个分割完成的列表。3.str.count(x)......
  • 力扣205(java)-同构字符串(简单)
    题目:给定两个字符串 s 和 t ,判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。每个出现的字符都应当映射到另一......
  • 常见距离算法
    机器学习中有很多的距离计算公式,用于计算数据和数据之间的距离,进而计算相似度或者其他。1.欧式距离(EuclideanDistance)​ 欧式距离是最常见的距离度量方法。小学、初中、......
  • Latex 如何写算法?推荐模板
    之前我已经在​​这篇文章​​总结了现有的算法包的区别。如果有选择苦难症的朋友可以考虑无脑使用以下模板来写算法。\usepackage[noend]{algpseudocode}#noend表示算法......
  • 计算空间物体包围球的两种算法实现
    详细介绍了计算空间包围球的两种算法。1.概述在进行二维空间几何运算的之前,往往会用包围盒进行快速碰撞检测,从而筛掉一些无法碰撞到的可能。而在三......
  • 浙江大学陈越老师《数据结构与算法》课程笔记
    目录1.1什么是数据结构1.1解决问题方法的效率1.2数据结构的定义1.3抽象数据类型1.2什么是算法1.2.1算法指标1.2.2复杂度的渐进表示法1.2.3例子—求最大连续子列和2......
  • 8.字符串容器string
    1.马上补充?.对于string中字母的大小写转换函数transform(str.begin(),str.end(),str.begin(),::tolower);//将str字符串中的大写转换为小写,保存在str中transform(st......
  • AcWing算法提高课 龟速乘(防止由于MOD过大使乘法爆long long)
    在求a*b%MOD的时候,如果MOD>1e10,则即便使用a%MOD*b%MOD,依旧有可能会爆longlong故可以利用和快速幂相似的思想,将乘法按位转化为加法,避免报longlong龟速乘模板:LLSlowM......