在字符串的操作中，对于子串的定位运算称为模式匹配。在没有进行任何优化和预先处理的情况下，查找str字符串中子串sub的的算法为：

       (1)初始化字符串str和sub的两个索引i=0,j=0；(2)比较str和sub中的i和j所索引的字符；（3）若相同，i和j分别加1，继续执行第二步；（4）若不同，则将i赋值为i-j+1，j赋值为0，继续执行第二步（如下图，即将str相对于sub向前移动一位，然后继续重新比较对应的字符）；（5）最终，若索引j到达了sub的末尾时，则字符串str包含子串sub，返回sub在str中的起始位置i-len_sub；（6）否则str字符串中未出现sub子串，返回-1。具体的算法使用C语言实现如下：

nkmp

int get_sub_pos(char *str, char *sub)
{
        int i = 0;
        int j = 0;
        int str_len = strlen(str);
        int sub_len = strlen(sub);
        while(i < str_len && j < sub_len) {
                if (str[i] == sub[j]) {
                        ++i;
                        ++j;
                } else {
                        i = i-j+1;
                        j = 0;
                }
        }
        if (j == sub_len) {
                return (i - sub_len);
        } else {
                return -1;
        }
}

       模式匹配算法KMP是一种预先对子串进行处理而实现优化的算法。KMP算法的思想是：当i=k，j=m，两个索引对应的字符不相同时，不需要回退i，而直接根据子串sub的特性，回退j即可。原因是：此时字符串str第k个索引之前的长度为m的字符串与字符串sub的前m个字符，已经做过比较，并且是相同的，我们只需要在sub字符串的前m-1个字符中找到另一个索引值next，保证字符串str第k个索引之前的长度为next的字符串和字符串sub的前next个字符相同，这样接下来比较i=k，而j=next处的字符即可。这里的next值只与sub字符串以及sub当前的索引值j有关，我们可以预先对sub字符串进行预处理，得到所有next的值，这样可以减少因回退i而增加的比较次数，从而优化匹配算法。

kmp

int get_sub_pos_kmp(char *str, char *sub)
{
        int i = 0;
        int j = 0;
        int next[SUB_MAX_LEN];
        int str_len = strlen(str);
        int sub_len = strlen(sub);
        get_next(sub, next);
        while(i < str_len && j < sub_len) {
                if (j == -1 || str[i] == sub[j]) {
                        ++i;
                        ++j;
                } else {
                        j = next[j];
                }
        }        
        if (j == sub_len) {
                return (i - sub_len); 
        } else {
                return -1;
        }
}

       那如何获取sub字符串的next值？可以通过类似递归的方式实现，首先当j=0时，next[j]=-1，表示当比较sub的第0个字符不相同时，无需next[0]值辅助，显然当j=1时，next[j]=0，表示当比较sub第1个字符不相同时，接下来比较sub的第j=next[j]，即j=0的情况。接下来假设当j=m时，next[j]=n,表示sub的前n个字符与索引m之前的前n个字符是相同的，此时：若sub[j+1]==sub[n+1],则sub的前n+1个字符与索引m+1之前的前n+1个字符是相同的，即next[j+1]=n+1;若sub[j+1]！=sub[n+1]，则sub的前n+1个字符与索引m+1之前的前n+1个字符不相同，接下来需要在前n个字符中寻找next[j]的值，即j=next[j],继续寻找。

void get_next(char *sub, int *next)
{
        int i = 0;
        int j = -1;
        int len = strlen(sub);
        next[0] = -1;
        
        while (i < len) {
                if (j == -1 || sub[i] == sub[j]) {
                        next[++i] = ++j;         
                } else {
                        j = next[j];
                }
                
        }
}

参考文档：

       1. 数据结构（C语言版） 严蔚敏 吴伟民 著