首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >模式串向右移动两个字符的位置继续进行

模式串向右移动两个字符的位置继续进行

原创
作者头像
用户7737280
发布2021-12-07 17:35:42
2960
发布2021-12-07 17:35:42
举报

因为模式串中的第一个字符是“a”,因此它无需再和这3个字符进行比较,而仅需将模式串向右滑动3个字符的位置继续进行i=7、j=2时的字符不比较即可。同理,在第一趟匹配中出现字符不等时,仅需将模式串向右移动两个字符的位置继续进行i=3、j=1时的字符比较。由此,在整个匹配的过程中,i指针没有回溯,如下图所示。

主串中第i个字符与模式串中第j个字符比较不等时,仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐,此时,模式串中头k−1个字符的子串t1t2…tk−1必定与主串中第$ i 个字符之前长度为k-1的子串“s_{i-k+1}s_{i-k+2}\ldots s_{i-1}”相等,由此,匹配仅需从模式串中第k个字符与主串中第i$个字符开始,依次向后进行比较。

因此不需要再和主串中第4个字符相比较,而可以将模式串向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说,若按上述定义得到next[j]=k,而模式串中tj=tk,则当主串中字符SiTj比较不等时,不需要再和Tk进行比较,而直接和Tnext[k]进行比较,换句话说,此时的next[j]应和next[k]相同。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档