文本串：aabaabaaf
模式串：aabaaf
- 前缀：包含首字母，但是不包含尾字母的所有连续子串
以模式串作为例子:
a
aa
aab
aaba
aabaa
- 后缀 ：只包含尾字母，不包含首字母的所有的连续子串
以模式串作为例子:
f
af
aaf
baaf
abaaf
如何求最长相等前后缀长度 ？
以模式串（aabaaf）作为例子:
a : 0
aa: 1
aab : 0
aaba: 1
aabaa:2
aabaaf : 0
前缀表是模式串用来回退的，它记录了模式串与文本串不匹配的时候，模式串应该从哪里开始重新匹配
前缀表里面存放的是最长相等前后缀的长度
用上面的例子，前缀表就是 010120
当模式串aabaaf与文本串在f的位置匹配冲突时， 去找最长前后缀相等的长度 ，长度就是需要跳转的下标
next数组 ：里面存放的元素就是前缀表 ，可能会对前缀表进行调整，具体例子具体分析
按照前后缀的定义来说，一个字符是没有前后缀的,至少得有两个字符才能比较前后缀的异同
如果是两个字符，前缀末位下标就是0,后缀末位下标就是1
leetcode28题为例
class Solution
{
public:
void getNext(vector<int> &next, const string& s)
{
//按照前后缀的定义来说，一个字符是没有前后缀的,至少得有两个字符才能比较前后缀的异同
//两个字符，前缀末位下标就是0,后缀末位下标就是1
//初始化
int j = 0;
next[0] = j;
for (int i = 1; i < s.size(); i++)
{
// 前后缀不同
while (j > 0 && s[i] != s[j])
{
// j向前回退
j = next[j - 1];
}
//相同的前后缀
if (s[i] == s[j])
{
j++;
}
// 将j（前缀的长度）赋给next[i]
next[i] = j;
}
}
int strStr(string haystack, string needle)
{
if (needle.size() == 0)
{
return 0;
}
vector<int> next;
next.resize(needle.size());
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++)
{
while (j > 0 && haystack[i] != needle[j])
{
j = next[j - 1];
}
if (haystack[i] == needle[j])
{
j++;
}
if (j == needle.size())
{
return (i - needle.size() + 1);
}
}
return -1;
}
};
如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！