首页 > 代码库 > KMP算法
KMP算法
KMP算法是一种改进的字符串匹配算法。适用于模式串P有循环重复段的情况下。
原理：
主串 S：S1, S2, …, …, …, …, …, …, Si-k+1, …, Si-1, Si
模式串P：(P1, P2, …, Pk-1,) Pk, …, (Pj-k+1, …, Pj-1,) Pj
Pj与Si不匹配，表示(Pj-k+1, …, Pj-1,) 与S匹配，而(Pj-k+1, …, Pj-1,) 与(P1, P2, …, Pk-1,)相同，所以(P1, P2, …, Pk-1,)与S也匹配，直接将模式串右移，将Pk与Si进行匹配，即j的next值为k。
public int index_KMP(char[] S, char[] P) { int len = P.length; int[] next = new int[len + 1]; get_next(P, next); int i = 0, j = 0; while (i < S.length && j < P.length) { if (S[i] == P[j]) { i++; j++; } else { j = next[j + 1] - 1; } } if (j == P.length) return i - P.length + 1; return 0;}
next函数：
next[1] = 0;
设next[j] = k;
if (Pk == Pj) next[j+1] = (k + 1 =) next[j] + 1;
else if (Pj == P(next[k]) next[j+1] = next[k] + 1;
else …
if (j == 0) next[j] = -1;
描述：j = 1时，next值为0；
j+1时，查看前一位j的值Pj与next[j]的值是否相同，若相同，从next[j]的下一位开始比较，若不相同，再查看Pj与next[j]的next[j]是否相同，一直到j==0，next[j]=-1。
private void get_next(char[] P, int[] next) { next[1] = 0; int i = 1; int j = 0; while (i < P.length) { if (j == 0 || P[i - 1] == P[j - 1]) { i++; j++; next[i] = j; } else { j = next[j]; } }}
举例：
KMP算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。