数据结构模式匹配求next值

发布网友发布时间：2022-04-23 03:40

共3个回答

热心网友时间：2023-10-13 15:11

看模式串'abcabcaaa'第1个没疑问next[1]=0，第2个字符b前一个字符为a，a前面没字符了，所以next[2]=0+1=1，第3个字符c,前面一个字符为b，b前面没有和他匹配的，那么next[3]=0+1=1，第4个a，前面个字符为c，c前面没有匹配字符，那么next[4]=0+1=1,第5个b，前面一个字符a有匹配的，长度为1，next[5]=1+1=2，第6个c,前面字符ab(长度为2)有匹配的,那么next[5]=2+1，以此类推得next[7]=4,next[8]=5,next[9]=2.

参考资料：ogin_u

热心网友时间：2023-10-13 15:12

只看模式串就可以了，比如
abcabcaaa，在第四个a发现不匹配的时候，由于前面是abca，这个与最开头的4个字符是相同的，所以直接判断与第五个字符是不是相同的，也就是是不是b。

热心网友时间：2023-10-13 15:12

寻找重复串就可以了吧，我算出来是—1 0 0 0 1 2 3 4 1