4.2.2 KMP算法上

    技术2022-07-11  94

    设计一个next数组,将一旦数组不匹配,j应该回溯到next的指针下

    因为第k个匹配不成功,说明1~k-1都是成功的

    移动思想:

    朴素模式是同时移动i,j让指向子串和主串的指针重新遍历,我们可以采用重新设计一个next数组,根据算法,只移动子串的指针j回溯到特定的位置,然后重新匹配

    next数组设计特点:

    next[1] = 0

    int Index_KMP(SString S,SString T,int next[]){ int i = 1; int j = 1; while(i<=S.Length&&j<=T.Length){ if(j==0||S.ch[i]==T.ch[j]){ i++; j++; } else{ j = next[j]; } } if(j>T.Length){ return i-T.Lenght; } else{ return 0; } }
    Processed: 0.013, SQL: 9