在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为（ ）。
- A.01111111
- B.01122341
- C.01234567
- D.01122334
正确答案及解析
正确答案
B
解析
KMP模式匹配算法通俗点说就是一种在一个字符串中定位另一个串的高效算法。其实我们在做这个题目时，也可以不需要知道KMP模式匹配算法，可以根据题目给出的定义式来求解。
当j=1时，很显然next[1]=0。
当j=2时，由于1＜k＜j，因此k无法取到合适值，因此next[2]=1。
当j=3时，k的取值为2，那么等号左边的‘P1P2…PK-1’字符串就是P1，为字符串中的第一个字符 a，而右边就是P2，即字符串中的第二个字符b，显然，它们不相等，因此next[3]=1。
当j=4时，k可以取值2或者3，取值为2时，等号左边为第一个字符a，而等号右边为 P3，也是字符a，因此相等，但这个时候我们还要判定当k取值为3时，等号左边为第一与第二个字符，即‘ab’，而右边为‘ba’，显然不相等，因此next[4]=2。
同理我们可以求得当j=5，j=6的结果，本题正确答案选B。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案