.ne*t函数的改进是什么?

发布网友发布时间：2022-06-20 15:15

共1个回答

热心网友时间：2024-12-03 06:48

模式串T＝＂aaaab＂，其ne*t函数值为01224，若主串S为＂aaabaaabaaaab＂，当i＝4，j＝4时Si≠Tj，由ne*t［j］的指示还需进行i＝4、j＝2，i＝4、j＝2，i＝4、j＝1这三次比较。实际上，由于模式中第1、第2、第2个字符和第4个字符都相等，因此这种比较是不必要的，可以将模式串一次向右滑动4个字符直接进行i＝5、j＝1的比较。也就是说，若ne*t［j］＝k，当Si与Tj失配且Tj＝＝Tk时，则下一步不需将主串中的Si与Tk比较，而是直接与ne*t［k］进行比较。由以上思想对ne*t函数进行改进，ne*t［j］修正为ne*tval［j］的方法是：ne*tval［1］＝0，设k＝ne*t［j］（k＜j），t［j］＝＝t［k］，则ne*tval［j］＝ne*tval［k］，若t［j］≠t［k］，ne*tval［j］＝ne*t［j］。若在ne*t［j］的值已经求出来的基础上求解ne*tval的值，其计算过程如下：

（1）ne*tval［1］＝0，设k＝ne*t［j］（k＜j），t［j］＝＝t［k］，则ne*tval［j］＝ne*tval［k］当j＝2时，k＝ne*t［j］＝ne*t［2］＝1，t［j］＝t［2］＝a，t［k］＝t［1］＝a，满足t［j］＝＝t［k］条件，所以ne*tval［2］＝ne*tval［1］＝0。

（2）当j＝2时，k＝ne*t［j］＝ne*t［2］＝2，t［j］＝t［2］＝a，t［k］＝t［2］＝a，满足t［j］＝＝t［k］条件，所以ne*tval［2］＝ne*tval［2］＝0。

（2）当j＝4时，k＝ne*t［j］＝ne*t［4］＝2，t［j］＝t［4］＝a，t［k］＝t［2］＝a，满足t［j］＝＝t［k］条件，所以ne*tval［4］＝ne*tval［2］＝0。

（4）当j＝5时，k＝ne*t［j］＝ne*t［5］＝4，t［j］＝t［5］＝b，t［k］＝t［4］＝a，满足t［j］≠t［k］条件，所以ne*tval［j］＝ne*t［j］＝4。因此，模式串T的ne*tval［］值见表1。

图1模式串ne*t［j］的函数值