模式串向右移动两个字符的位置继续进行
2023-04-18 14:11:02 时间
因为模式串中的第一个字符是“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,则当主串中字符Si和Tj比较不等时,不需要再和Tk进行比较,而直接和Tnext[k]进行比较,换句话说,此时的next[j]应和next[k]相同。
相关文章
- 中国程序员视角下的英文命名
- 三分钟回顾!12月云计算领域重要动态速览
- 2020上半年,云运营服务市场规模为100.8亿元
- 一个简单需求竟让我改了十几处代码,万字控诉到底什么是重复代码!
- IDC AI云服务报告:阿里语音AI、对话式AI市场份额再次位居第一
- 如何消除代码屎山中的一大坨参数列表?
- “按需定制”灵活部署,京东智联云“云服务”实力圈粉
- Aruba 收购Silver Peak 强化边缘服务平台
- 第一个只出现一次的字符位置
- 一文带你读懂什么是云计算,发展历程及现状分析,值得收藏
- 【RASA】DIET:Dual Intent and Entity Transformer
- 关于使用线程需要注意地方,你都知道吗?
- 《代码重构》之方法到底多长算“长”?
- 假如重新设计Kubernetes
- 美国法院叫停TikTok禁令 本周日正式生效
- 赋能商用车数字化变革,福田汽车智云(FOTON-ICLOUD)工业互联网品牌重磅发布
- 包含 min 函数的栈
- 7个必备的云基础设施自动化工具
- 今年上半年中国云运营市场实现增长
- 你真的思考过自己写的代码为啥这么垃圾吗?