1.BF算法
Brute Force(暴力)算法，我们的目的是查找两个字符串中一个字符串是否是另一个字符串的真子集，为了便于区分，我们把前者称为str2，后者称为str1，那么我们的目的就是就是在str1中找到字符串str2。
例1：假设str1[10] = "abcdef"; str2[10] = "bcd";
最开始的时候，str1和str2都指向字符串的首元素，对于这个例子，我们很容易想到一种方法，就是直接比较str1和str2指向的元素，当 *str != *str2时，str1++，str2不变，直到*str1 == *str2时，str1和str2同时加一，然后继续比较，当str2指向的元素为'\0'的时候说明字符串str2比较结束，并且在此之前，str1中能找到一个子串与str2相同，说明能找到。这种算法对于这个例子来说，能够实现我们所需要的功能。
例2：假设str1[10] = "abbbcdef"; str2[10] = "bbc"; 时，上述的方法就不再适用。
对于这个例子，如果沿用例1中的方法，当str1指向前两个b的时候，都是没有问题的但是当str2指向c，str1指向第三个b的时候发现匹配失败，然后str1就会继续向后走，直到结尾，然后会得到匹配失败的结果，但是很明显，我们能看到在str1中是能够找到str2的，所以一定是我们的算法出现了问题， 仔细一想我们就会发现，如果按照例1的方法，当第一个字符匹配成功后，如果后面的字符中由不同的字符，那么匹配就会失败。所以我们应该将主串的每一个字符看作一个字符串的开通头，即当遇到第一个*str1 == *str2 时，记住str1指向的位置，然后str1和str2继续加1，直到str1或者str2结尾，如果中途遇到*str1 != *str2 ，将str1回退到记住的位置，然后加1，str2回退到起始位置，然后继续匹配，循环往复，直到匹配成功或者字符串结尾。
模拟实现strstr，查找得知函数原型为char* strstr(const char* str1, const char* str2);
2.kmp算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。
以上说法来自于百度百科，KMP算法和BF算法根本的区别就是主串不回退，子串不回退到初始位置。
此时匹配不成功，但是我们发现主串34位置与子串的01位置是相同的，那么我们是不是就可以省略子串01位置的匹配过程。此时j回退到2的位置就可以了，那么我们怎么知道匹配失败以后需要回退到哪个位置?这就引入了next数组的概念。我们用一个数组来存放当匹配失败以后子串需要回退的下标。
但是，next数组中的元素是怎么求的呢？规则是在匹配成功的部分中找到两个以下标为0的字符开头，j-1字符结尾的真子串，然后next数组中的值即为这个真子串的长度。
例如："ababcabcdabcde"这个字符串的next数组中的值即为：-1 0 0 1 2 0 1 2 0 0 1 2 0 0
"abcabcabcabcdabcde"这个字符串的next数组中的值即为：-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
到此，next数组的求法我们已经掌握，但是在计算机中实现，我们不能一个一个求，又因为由简单的推理得知next[0] = -1,next[1] = 0是恒成立的，所以我们只要给出next数组的递推公式就可以啦。即：已知next[i] == k;怎么求next[i+1] = ?
我们假设next[i] = k成立，那么就有str[0] ... str[k-1] = str[x] ... str[j-1]，此时如果str[i] == str[k]，那么，就有str[0] ... str[k] = str[x] ... str[j]，又因为两个子串完全相同，所以长度也相同，因此就有k-0=j-x，==> x = j-k，所以next[i+1] = k+1；如果str[i] != str[k]，那么k就要回退到next[k],然后继续比较。直到k大于子串长度时，匹配成功，或者主串结束。
对于上述next数组，我们其实还可以优化，例如对于字符串aaaaaaaab，，它的next数组为-1，0，1，2，3，4，5，6，7，优化后的nextval数组为：-1， -1， -1， -1， -1， -1， -1， -1， 7，为什么会出现优化后的数组呢？对于上述示例，假设在 5 号处失败了，那退一步还是a，还是相等，接着退还是 a。那么我们很轻松的可以得出nextval数组求法即是如果当前回退的位置，正好是和当前字符一样，那么就写那个字符的nextval的值，否则就写自己的。
