title: KMP模式匹配算法
date :2019-02-1021336056336042
目录前言一般的模式匹配算法KMP模式匹配算法假设next数组利用next数组进行模式匹配的详细代码
前言
KMP是模式匹配算法，什么是模式匹配呢？ 也就是说，现有的模式串(字符串)在另一个主列中查找是否存在与模式列相等的子列(由主列中的任意连续字符构成的子列)。
该算法的有用性广泛，是正则表达式的基础。
例如，假设您想要知道是否有字符串“ababcabcacbab”，并且该字符串中是否有字符串“abcac”。 这叫做模式匹配。
常规模式匹配算法的经典模式匹配是将模式列的第一个字符从主列的第一个字符向右匹配。
匹配的规则如下
在主字符串的第I个位置，pos=i，主字符串的pos位置的字符与模式列的第一个字符相等时，pos与模式列的第二个字符一致。 另外，相等时，在与图案列最后一致之前持续向下方一致，意味着在主列中存在该图案列； 如果不相等，则停止匹配，返回主字符串，排列I。 然后，假设pos=i，并重复上述步骤直到I到达主字符串的末尾。 对应的代码如下。
# include stdio.h # include string.hint main () charstr(10000 )，pat (10000 )； printf (pleasepushthemainstring : (n ) )； scanf('%s '，str )； printf (pleasepushthepattern : (n ) )； 扫描(' % s '，pat )； intlens=strlen(str )，lenp=strlen ) ) pat； //从主串的第一个位置向后匹配，最后的for(intI=0； ilenS I ) { int pos=i，j=0； while(JLenp )//如果主串的pos位置等于图案串的j位置，则均为低位if(pat[j]==str[pos] ) j； 销售点； //否则中断与模式列的匹配的else break； //判断是否与模式列完全一致，一致时为I位置if(pos-I==lenp ) printf ) (npatternstartin%d )，I )； }经典的模式匹配算法有一个缺点，就是每次匹配失败时都要追溯到主串中的I位置。
例如，如果主字符串为“000000000000000000001”，而图案字符串为“0001”，则匹配正确的上一个匹配将追溯到图案字符串的最后一个字符。 这之中不能轻视浪费的时间。
有不能追溯的算法吗？
KMP模式匹配算法KMP算法的优点是不使用回溯，以滑动方式对模式序列进行下匹配。
假设next数组，首先假设在模式串上有next数组。
该数组值意味着模式列的第0位以后的长度为next[j]的字符串和第j位(从0开始，除去0 )之前的长度为next[j]的字符串相等，同时也表示next
例如，abcac模式列的next数组值依次为[-1、0、0、0、1]。 图案中的第4位(从0开始)字符c的next值为1表示字符c的前面的长度为1的字符串a与字符c的前面的长度为0位到长度为1的字符串a相等。 除了剩下的位、0位以外，next值都是0。
例如，0001模式列的next数组值依次为[-1、0、1、2]。
在使用next数组的模式匹配的常规模式匹配中，如果主串的pos位和模式串的j位不匹配，则主串返回i 1位，并且模式串的0位再次匹配。
如果有next数组，就不需要追溯到i 1位进行重新匹配。 而是使用主串pos位和模式串next[j]位进行匹配，如果仍然不匹配，则转移到next[next[j]]。 模式列滑动到主列pos 1位并重新匹配，直到next的值为-1。
实际上，在与求出next[j]的值不一致的情况下，是使模式列向下滑动的过程。 其原理源于next数组的特殊性。
模式列第0位后的长度为next[j]的字符串和第j位(从0开始，除0以外)前的长度为next[j]的字符串大。
将代码# include stdio.h # include string.h # include stdlib.h//模式列同时视为“主列”和模式列，并同样根据KMP算法匹配next值voidgetnext(char*str，int *next
,int n) { next[0]=-1; int i=1; int j=-1; while (i<n) { // 如果j==-1，则“主串”i位置的next值为0。 // 前进到“主串”的下一位，并使模式串从头开始匹配 if (j == -1) { next[i]=0; i++; j=0; } // 如果“主串”i位置的前一位和模式串j位置相同，则“主串”i位置的next值为j+1。 // 同时“主串”与模式串继续向下匹配。 else if (str[i-1] == str[j]) { next[i]=j+1; i++; j++; } // 如果不匹配，则前进到模式串的next[j]位置 else j=next[j]; }}int main() { char str[10000],pat[10000]; printf("please push the main string:n"); scanf("%s",str); printf("please push the pattern:n"); scanf("%s",pat); int lenS=strlen(str),lenP=strlen(pat); // next数组：当模式串第j位与主串当前第i位不匹配时，将模式串向后滑动， // 用模式串中第next[j]位再与主串中的第i位比较。 // 若next[j]==-1，则将模式串整体向后移动一位，与主串中第i+1位继续比较。 int *next=(int*)malloc(sizeof(int)*lenP); getNext(pat, next, lenP); int i=0,j=0; // i为主串中字符位置，j为模式串中字符位置 while (i<lenS) { // 如果j==-1，则模式串整体向后移动一位，与主串中第i+1位比较 if (j == -1) { i++; j=0; } // 如果主串i位置与模式串j位置相等，则i、j都向下继续配对 else if (str[i] == pat[j]) { i++; j++; if (j == lenP) { printf("find pattern in %dn", i-lenP); j=0; } } // 如果模式串j位置与主串i位置不匹配，则将模式串向后滑动， // 用模式串的next[j]位置与主串i位置匹配 else j=next[j]; } free(next); return 0;}