strStr()函数的定义:
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
现在我们来介绍一下实现这个函数的三种方法（采用的语言为C++）
对不齐可不能怨我哦，写的时候是对齐的。。。
文章目录
暴力解法
暴力解法也就是所说的移动窗口，将needle的0下标与haystack的0下标对齐，然后一一对比每一个字符，如果有一个字符不匹配，就把needle的0下标与haystack的1下标对齐，接着进行一一对比。。。。。。以此类推（注意不要越界），直到needle的所有字符都与haystack里的字符对应，就返回此时needle的0下标对应的haystack下标；如果，到最后也没有匹配成功，就返回-1
int strStr(string haystack, string needle)
{
if (needle.empty())return 0;
for (int i = 0; i <= (int)(haystack.size()-needle.size()); i++)
{
bool flag = true;
for (size_t j = 0; j < needle.size(); j++)
if (haystack[i + j] != needle[j])
{
flag = false;
break;
}
if (flag)return i;
}
return -1;
}
由于c++的string类都以’\0’结尾，恰好符合这个算法，所以
for (int i = 0; i <= (int)(haystack.size()-needle.size()); i++)
可以改写为
for (size_t i = 0; i <= haystack.size(); i++)
不理解的可以自行推导一下
时间复杂度O(mn),m是haystack的长度，n是needle的长度
空间复杂度O(1),没有使用额外的空间
KMP算法
看完暴力解法，不知道有没有发现一个很有意思的点,如果
haystack是"aaaaaaaaaaaaaab"
needle是"aaaab"
这时候我们再用暴力解法就显得很傻*，因为进行了很多没有意义的操作，KMP算法就是来解决这个问题的，对于needle字符串，如果存在多个重复的字符或者字符组也就是所谓的公共前后缀
公共前后缀：
“abca” --> “a”
“abhab” --> “ab”
对于一个字符串"aaaab",这里看的并不单单是整个字符串的公共前后缀，而是前string.size()个字符的公共前后缀
公共前后缀是不包括自身全部的。不要因为这个看不懂下面的
“a” --> “” 前一个
“aa” --> “a” 前两个
“aaa” --> “aa” 前三个
“aaaa” --> “aaa” 前四个
”aaaab“ --> “” 前五个
是不是不知道这个有什么用，别急，这个就是KMP算法的核心，***通过构造回溯数组***来优化暴力解法
现在来构造回溯数组
vector<int> makeNext(string needle)
{
int pre = -1,
rev = 0;
vector<int> arrayNext(1, -1);
while (rev < (int)needle.size())
{
if (0 > pre || needle[pre] == needle[rev])
{
pre++;
rev++;
arrayNext.push_back(pre);
}
else
pre = arrayNext[pre];
}
return arrayNext;
}
字符串 "a a a a b"
回溯数组 -1 0 1 2 3 0 （这里的-1是为了运算而添加的）
回溯数组的下标对应的就是前n个字符的公共前后缀，有兴趣的话可以看一下回溯数组的构造代码，自己推敲一遍
现在，让我们回到最初的问题
haystack是 “aaaaaaaaaaaaaab”
needle是 “aaaab”
现在开始一一匹配
aaaaaaaaaaaaaab
aaaab
匹配到这里的时候出现字符不匹配的情况，此时b的下标是4，于是在回溯数组里找到对应下标的数据为"3"，转换到第四个字符
aaaaaaaaaaaaaab
aaaab
此时匹配，进行下一个字符比较
aaaaaaaaaaaaaab
aaaab
此时又出现不匹配情况，接着跳转
aaaaaaaaaaaaaab
aaaab
。。。。。。
以此类推到最后
aaaaaaaaaaaaaab
aaaab
全部匹配，结束
时间复杂度为O(n)
空间复杂度为O(1)
现在是不是还没有明白，下面再举一个例子
haystack ”abcabcabcp“
needle “abcabcp”
回溯数组为[-1, 0, 0, 0, 1, 2, 3, 0]
可以很容易的看出，正确的匹配在最后，现在开始一一匹配
abcabcabcp
abcabcp
匹配到这里出现不匹配情况，但是，”p“之前的”abcabc“都是匹配的且公共前后缀是3，那就可以把第二个”abc“当作开头，直接跳到
abcabcabcp
abcabcp
然后再一路匹配下去
int strStr(string haystack, string needle)
{
if (needle.empty())return 0;
vector<int> arrayNext = makeNext(needle);
int i = 0,
j = 0;
while (i < (int)haystack.size() && j < (int)needle.size())
{
if (j < 0 || haystack[i] == needle[j])
{
i++;
j++;
}
else
j = arrayNext[j];
}
return j == needle.size() ? i - needle.size() : -1;
}
时间复杂度O(n)(最好情况)，O(mn)(最坏情况)
空间复杂度O(n)构造了一个和needle一样大小的回溯数组
Rabin Karp算法
其实kmp算法在乱序情况下和暴力解法相差不大，局限性很大，但是Rabin Karp算法（以下称为R算法），是真正的封神算法
haystack ”abcabcabcp“
needle ”abcp“
因为我们的搜索基本上包含的字符都属于ASCII表里的内容，而大多数情况下是a~z的26个小写字母，这里为了简单，就假定字符串只包含26个小写英文字母（如果有兴趣的话可以我的基础上进行拓展）。
对于needle字符串，”abcp“，转化为[0, 1, 2, 15]，转换原理就是把每个字符对应的ASCII值减去”a“的ASCII值也就是97。
long long a = 0*pow(26,3) + 1*pow(26,2) + 2*pow(26,1) + 15*pow(26,0)
此时a的值就是needle这个字符串的自定哈希值
使用这个步骤来计算haystack前4个字符的哈希值，与a进行对比，如果相等则返回下标，如果不相等，则计算第二个字符到第5个字符这四个字符的哈希值，可能会有人会问，那这个时间复杂度岂不是还是很高，对，如果这样的话，和暴力解法就一样了，但是，如果细心一点就可以发现，第一个4字符哈希值和第二个4字符哈希值之间存在联系。
设第一个4字符哈希值 a = 10
设第二个4字符哈希值 b
b = a * 26 - haystack[0] * pow(26,4) + haystack[4]
通过这样就可以进行复杂度为1的下一个哈希值运算
但是又会有一个新的问题，就是数据太大，long long已经装不下，这个在python里面还好不需要考虑，但是在c，java里是必须考虑的，那就对哈希值取模（余）呗，理论上，除数越大，越不容易出现两个字符串哈希值相同的情况，这里取2的63次方
int strStr(string haystack, string needle)
{
if (needle.empty())return 0;
if (needle.size() > haystack.size())return -1;
long long modulus = (long long)pow(2, 63);
int capacity = 26;
long long hayHashnum = 0, needHashnum = 0, aL = 1;
for (size_t i = 0; i < needle.size(); i++)
{
hayHashnum = (hayHashnum * capacity + haystack[i] - 'a') % modulus;
needHashnum = (needHashnum * capacity + needle[i] - 'a') % modulus;
aL = (aL * 26) % modulus;
}
for (size_t i = 0; i <= haystack.size() - needle.size(); i++)
{
if (hayHashnum == needHashnum)return i;
hayHashnum = (hayHashnum * capacity - ((long long)haystack[i] - 'a') * aL + haystack[i + needle.size()] - 'a') % modulus;
}
return - 1;
}
时间复杂度O(n)，只遍历了一遍
空间复杂度O(1),没有使用额外空间
= needHashnum)return i;
hayHashnum = (hayHashnum * capacity - ((long long)haystack[i] - ‘a’) * aL + haystack[i + needle.size()] - ‘a’) % modulus;
}
return - 1;
}
***时间复杂度O(n)，只遍历了一遍***
***空间复杂度O(1),没有使用额外空间***
------
好了，这就是strStr()的三种实现方式，如果还有更好的想法，在评论区里留言哦~~