本文共 1384 字，大约阅读时间需要 4 分钟。
本人愚笨，CSDN上看了很多解法都不了解，而且很多解法都有些问题。自己看了书研究了一个晚上才大概明白了这一原理。特此附上自己写的解法和见解。
KMP是对于字符串匹配蛮力解法的一个改进，原理就是在求出模式子串自己内部的重复模式，举个简单的例子，主串S[] = "ababaababcb"子串T[] = “ababc”,T[0]~T[1] = T[2]~T[3]，如果前次比较主串已经有S[0]~S[3]匹配上了子串T[0]~T[3]，只是S[4]与没有匹配上，就有S[2]~S[3]是等于T[0]~T[1]的，那么就可以略过，而直接比较S[4]与T[2]了。
而求数组next[]本质就是求子串的重复模式。
#include经测试，代码没有问题。#include #include int *getnext(char *cht);int main(int argc, char *argv[]){ if (argc != 3) { printf("usage:%s Mstring Tstring.\n",argv[0]); exit(1); } int slen = strlen(argv[1]); //主字符串 int tlen = strlen(argv[2]); //模式字符串 char *chs = (char *)malloc((slen+1)*sizeof(char)); char *cht = (char *)malloc((tlen+1)*sizeof(char)); strcpy(chs,argv[1]); strcpy(cht,argv[2]); //获得next int *next = getnext(cht); //匹配 int index=-1, i=0, j=0; while (chs[i]!='\0' && cht[j]!='\0') { if (chs[i] == cht[j]) { i++, j++; } else { j = next[j]; if (-1 == j) i++, j++; } } if (cht[j] == '\0') index = i - tlen; printf("index = %d\n",index+1); return 0;}int *getnext(char *cht){ int tlen = strlen(cht); int j=1, k=-1; int *next; next = (int *)malloc(tlen*sizeof(int)); if (NULL == next) { perror("malloc"); exit(1); } next[0] = -1; while (j
转载地址：http://zemws.baihongyu.com/