首页 > 代码库 > KMP匹配算法
KMP匹配算法
KMP算法可以在O(n+m)的时间数量上完成串的模式匹配操作。
n指的是主字符串的长度，m指的是模式字符串的长度。
求next数组的算法：
void get_next(char T[], int next[]) { i = 1; next[1] = 0; j = 0; while( i <= T[0]) { if(j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; }}
KMP匹配算法：
int KMP(char S[], char T[], int next[], int pos) { i = pos; j = 1; while(i <= S[0] && j <= T[0]) { if(j == 0 || S[i] == T[j]) { ++i; ++j‘ } else j = next[j]; }}
KMP算法的主要优点是主串不回溯，且在主串与子串有很多“部分匹配”时才显得快。
KMP匹配算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。