数据结构考研分类复习真题 第四章 串[9]

．在字符串模式匹配的KMP算法中求模式的next数组值的定义如下【北京邮电大学 二（分）】

next［j］=

请问

（）当j=时为什么要取next[]=？

（）为什么要取max{K}K最大是多少？

（）其它情况是什么情况为什么取next[j]=?

．给出KMP算法中失败函数f的定义并说明利用f进行串模式匹配的规则该算法的技术特点是什么？【东南大学 一 （分） 一 （分） 一 （分）】

． 在模试匹配KMP算法中所用失败函数f的定义中为何要求pp……pf(j)为pp……pj两头匹配的真子串？且为最大真子串？ 【东南大学 一（分）】

．如果两个串含有相等的字符能否说它们相等？【西安电子科技大学 软件 一 （分）】

．设SS为串请给出使S//S=S//S成立的所有可能的条件（//为连接符）【长沙铁道学院 三 (分)】【国防科技大学 一 】

．已知s ＝（xyz）＋＊t ＝（x＋z）＊y试利用联结求子串和置换等基本运算将 s 转化为 t 【北方交通大学 一（分）】【山东科技大学 一 （分）】

[] [] [] [] [] [] [] [] [] [] [] []