大学士考试网

考研动态 考研英语 考研政治 考研数学 专业课 模拟试题 历年真题

2014年考研数据结构辅导(19)

专业课  时间: 2019-03-09 12:17:11  作者: 匿名 

空格串是指__由空格字符(ASCII值32)所组成的字符串,其长度等于  空格个数____。

在模试匹配KMP算法中所用失败函数f的定义中,为何要求p1p2……pf(j)为p1p2……pj两头匹配的真子串?且为最大真子串?  

失败函数(即next)的值只取决于模式串自身,若第j个字符与主串第i个字符失配时,主串不回溯, 模式串用第k(即next[j])个字符与第i个相比,有‘p1…pk-1’=‘pj-k+1…pj-1’,为了不因模式串右移与主串第i个字符比较而丢失可能的匹配,对于上式中存在的多个k值,应取其中最大的一个。这样,因j-k最小,即模式串向右滑动的位数最小,避免因右移造成的可能匹配的丢失。

猜你喜欢

精选专题