Question

模式串 P = 'abaabcac'的 next 函数值序列为 答案

Answer 1

模式串 P = 'abaabcac'的 next 函数值序列为01122312。

前两个字母next序列分别为01；

第三个"a"  时，它前一个字母为b，从头开始字母为a， a!=b所以为1；

第四个"a"  时，前字母为a，从头开始字母为a，a=a，所以值为1＋1=2（相等时为串长加1）；

第五个"b"，前个字母为a，从头开始a，a=a，为2；

第六个"c"，前个字母为b，再往前是a，ab，从头开始ab串，ab=ab，因此值为2＋1＝3；

第七个字母为"a"，前个字母为c，与从头开始的第一个字母不相等，所以为1；

第八个为"c"，前个字母为a，与开始第一个字母相等，因此为2。

扩展资料：

朴素的模式匹配算法

算法思想：从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

若模式子串的长度是m,目标穿的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法的时间复杂度为O(mn)。

朴素的模式匹配算法中存在回溯，这影响到匹配算法的效率，因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法，KMP算法和BM算法均为无回溯的匹配算法。

参考资料来源：百度百科-模式匹配

Answer 2

abaabcac
01122312
前两个字母next序列分别为01,直接写上
第三个"a" 时，它前一个字母为b,从头开始字母为a, a!=b所以为1
第四个"a" 时，前字母为a,从头开始字母为a,a=a,所以值为1＋1=2（相等时为串长加1）
第五个"b"，前个字母为a,从头开始a,a=a,为2
第六个"c",前个字母为b,再往前是a,ab,从头开始ab串，ab=ab，因此值为2＋1＝3
第七个字母为"a",前个字母为c,与从头开始的第一个字母不相等，所以为1
第八个为"c",前个字母为a,与开始第一个字母相等，因此为2

Answer 3

模式串P=‘abaabcac”的next函数值序列为 -1 0 0 1 1 2 0 1

Answer 4

abaabcac
-10-1102-11
前两个字母next序列分别为-1和0,直接写上
第三个"a"时，它与首字母相同且只隔一个字符,所以为-1
第四个"a"时，它与首字母相同且前一字母为a,与第一字母相同,所以值为1
第五个"b"时，前个字母为a,与第一字母相同,继续判断p[1]=b和p[4]=b相同，所以为0
第六个"c"时,前2个字母为ab,与第一和第二字母相同,继续判断p[2]=a和p[5]=c不相同,因此值为2
第七个"a""时,它与首字母相同且前面没有与头部相同的字符串，所以为-1
第八个"c"时,前个字母为a,与第一个字母相同，因此为1