题目描述：有两个字符串s和s1,寻找s子串在s1中第一次出现的位置，如果没有则返回-1，若s1为空，则返回0.
我自己的解法
循环遍历字符串s，当s[i] == s1[0]，即第一个字符相等时，就在来一轮循环，按个比较每个字符是否相等，若相等则返回i - s1.size()，若不相等，则回退i到i - j.
当整个字符串匹配成功时，我们有右边的
i，因为一共匹配了s1.size()次，所以想要求到开始的索引，只需减去s1.size()当只匹配了一部分时，有图不难看出，将
i回退到i - j即可
class Solution
{
public:
int strStr(string haystack, string needle)
{
if (needle == "")
{
return 0;
}
int i = 0;
int j;
bool is_substr = true;
while (i < haystack.length())
{
if (haystack[i] == needle[0])
{
for (j = 0; j < needle.size(); j++, i++)
{
if (needle[j] != haystack[i])
{
is_substr = false;
break;
}
}
if (is_substr)
{
return i - needle.size();
}
else
{
is_substr = true;
i = i - j;
}
}
i++;
}
return -1;
}
};
宫水三叶的题解 （KMP算法）
原链接,可以自己去看一下，写的真的很好。膜大佬orz
文章关于KMP算法已经是说的比较清楚了，我下面单纯补充几点我当时的困扰
前缀和后缀
前缀和后缀是不包括整个单词的，例如单词read,r,re,rea都是前缀，但是read就不能算前缀，后缀也是同理为什么需要两个指针j ，i
j指向已经匹配成功字符串的末尾，i用于遍历匹配串，指向下一个要匹配的字符
3.next数组里的数字到底是什么意思
next[i]里的数字是指当在第i个字符匹配失败时，此时的最大的相同前后缀的长度。
-
next函数的编程实现
图片用的是宫水三叶题解里的图，我对这些图做一些解释
image.png
next[0] = 0, 因为在0号位置失败的话，前后缀长度为0
当p[i] == p[j]时，即两个字符匹配成功时，此时相同前后缀长度就可以加一，此时的j指向是最长前缀的末尾，所以next[i] = j + 1
当p[i]和p[j]不相等的时候，按照KMP算法，我们就要回退，因为加了一个字符就不相等了，所以我们稍微放宽一点要求，匹配不了长度为j的一整个字符串，可能可以匹配 j个字符的开头的一部分，所以我们试试next[j - 1],本质上是试试公共前缀的公共前缀行不行，不行就在回退，直到匹配上了，或是j变成了0，无法再匹配。
ps:如果对于j = next[j - 1]不明白看这篇，要是还看不懂，那就多看几遍吧.
// KMP
class Solution1
{
public:
int strStr(string s, string p)
{
int n = s.size(), m = p.size();
if (m == 0)
return 0;
//设置哨兵
s.insert(s.begin(), ' ');
p.insert(p.begin(), ' ');
vector<int> next(m + 1);
//预处理next数组
for (int i = 2, j = 0; i <= m; i++)
{
while (j and p[i] != p[j + 1])
j = next[j];
if (p[i] == p[j + 1])
j++;
next[i] = j;
}
//匹配过程
for (int i = 1, j = 0; i <= n; i++)
{
while (j and s[i] != p[j + 1])
j = next[j];
if (s[i] == p[j + 1])
j++;
if (j == m)
return i - m;
}
return -1;
}
};
