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。