如何匹配某字符串,字符串匹配怎么输入

首页 > 实用技巧 > 作者:YD1662024-02-03 04:14:10


我们再观察下面的情况,我们发现文本串中字符“A”和模式串中的字符“B”匹配失败,此时已匹配的后缀“AB”我们可以在模式串中找到同样的子串“AB”,我们完全可以向后移动模式串,将两个串中的“AB”来对齐,再继续匹配。

如何匹配某字符串,字符串匹配怎么输入(21)


再观察下面这种情况,已经匹配的后缀“CBAB”我们无法在模式串中找到同样的部分,难道就没有办法加快匹配了吗?我们以匹配的字符串“CBAB”中的几个真后缀“BAB”、“AB”、“B”,其中“AB”作为前缀出现在了模式串中,那我们可以后移模式串,将文本串中的后缀“AB”和模式串中的前缀“AB”对齐,从而继续进行匹配。

如何匹配某字符串,字符串匹配怎么输入(22)


为什么已匹配的字符的真后缀必须要和模式串中的前缀匹配才可以移动呢?我们可以看下面这个例子。已匹配的“CBAB”中的真后缀“AB”,在模式串中是存在的(非前缀),那我们向后移动模式串把这两部分对齐继续匹配如何呢?这样做看似合理,但实际上却是一个无效的匹配位置。很明显,因为文本串中“AB”前的字符和模式串中“AB”前的字符一定是不匹配的,否则我们是可以找到一个比“AB”更长的匹配,且这个匹配的一定是模式串中的前缀,这就符合我们上面说的情况了。所以当没有能够匹配上合理后缀这种情况出现时,正确的移动是将模式串向后移动m位。

如何匹配某字符串,字符串匹配怎么输入(23)


总结:1.当模式串中有子串和已匹配后缀完全相同,则将最靠右的那个子串移动到后缀的位置继续进行匹配。

如何匹配某字符串,字符串匹配怎么输入(24)

上一页23456下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.