字符串_KMP
void get_next (String T, int next[]){ int i = 1, j = 0; next[1] = 0; while (i < T.length){ if (j == 0 || T.ch[i] == T.ch[j]){ ++ i; ++ j; next[i] = j; } else j = next[j]; } }
对于一个字符串,从第二个开始寻找他的最大相同前后缀,实现代码为以上部分,对于连续的前后缀只需要next[i-1]+1便可以获得当前字符的next序列,如果当前字符在期望的相同前后缀中找不到对应的字符(即T[I]!=T[j])则返回j=next[j-1],再对T[j]与T[I]进行判断,向前寻找是否存在一个相同前后缀;
int Index_KMP (String S, String T, int next[]){ //S为长串,T为短串 int i = 1, 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.length; else return 0; }
从主串的头开始进行判断,当副串的的字符与主串的字符不对应时,找到副串该字符位置对应的next表,副串对应主串的位置跳跃next表对应的单位字符,再次从跳跃位置开始继续对应,反复上述操作,直到找到主串中能够与副串完全匹配的字符串的位置