这一题可以说是做题以来收获最大的一道题了，虽然它是放在简单题范畴里的，但是它同样可以用较厉害的算法解答。当然，我只会暴力解答。
暴力的代码就不放了。
这道题我目前能够写出三种答案：
①暴力解答；
②直接调用内置函数；
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};
③利用KMP算法
（之前从没了解过，这也是我今天做题最大的收获）
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
vector pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
};
按照我的理解大概解释一下KMP算法，当然，我主要是记录，并不能讲的多清楚。
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
vector pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
代码的上半部分，用一个数组来记录needle字符串的各个长度的相同的最长前缀和最长后缀的长度——n；
例：输入needle=aacbacaa;
那么"a"——n=0;
"aa"——n=1；
“aac”——n=0;
……
“aacbacaa"——n=2;
分别将以上结果输入pi数组中；
则得到needle各个长度所对应的最长前缀和最长后缀的长度——n；
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
下半部分代码与上半部分代码相似，但是却有些不同；
我以画图的形式大概讲述：
输入haystack为”abacababca“
输入needle为“abab”
开始作比较，当作比较到第四位时，"b"!="c"；
得到"aba"的n值，即n=1；
则以以下形式开始下一轮比较，以此类推，直至结束；
再次比较出不等：
找到对象，返回对应值。
虽然讲的不是很清楚，但是我觉得图片能说明的事情已经挺多的了！
加油~！
