模式匹配
模式匹配即字符串匹配,表示在一个大的字符串T之中查找某个字符串P的出现位置的运算。
这里T称之为文本串(主串),P称之为模式串
通常主串的索引用i
表示
模式串的索引用j
表示
前缀、后缀
对于一个有n个字符的文本串,它有n-1
个前缀和n-1
个后缀
如aabcada
它的前缀:[a
,aa
,aab
,aabc
,aabca
,aabcad
]
它的后缀:[a
,da
,ada
,cada
,bcada
,abcada
]
BF算法
匹配失败:
主串索引i
回溯到i-j+2
模式串索引j
回溯到j+1
KMP算法
匹配失败:
主串索引i
无需回溯
模式串索引j
回溯与模式串本身有关(j
的下一个位置next[j]
)
next[j]的计算方式
比如模式串:abcaabb
索引j
从1开始
经如下计算得出next[j]
= 0111223
例题:
因为用了KMP算法,因此需要先计算出next[j]
= 011223
第一次失配时 i = j = 5,i 不需要回溯,所以 i = 5
j 回溯到 对应的 next[j]
所指向的位置,即 next[5] = 2, 回到索引为2的位置
因此答案选C
nextval的计算方式
例题:
参考资料:【数据结构 串 KMP算法 next和nextvel】 https://www.bilibili.com/video/BV1PG4y1V7Zq/?share_source=copy_web&vd_source=e22a75a6781804ee25ce46a2afc235ce