日野弥生：勉強しよう
KMP
发表于2024年12月29日
介绍
在字符串中查找子串：Knuth–Morris–Pratt 算法,该算法由 Knuth、Pratt 和 Morris 在 1977 年共同发布。该算法是前缀函数的一个典型应用。
过程
（KMP）算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 𝑂(𝑚+𝑛)。
实现
class Solution {
private:
std::vector<int> m_NextArr;
public:
void buildNext(string needle)
{
m_NextArr.push_back(0);
int prefixLen = 0,i=1;
int n=needle.size();
while(i<n)
{
if(needle[prefixLen] == needle[i])
{
prefixLen++;
m_NextArr.push_back(prefixLen);
i++;
}
else
{
if(prefixLen)
prefixLen = m_NextArr[prefixLen -1];
else
{
m_NextArr.push_back(prefixLen);
i++;
}
}
}
}
int strStr(string haystack, string needle) {
buildNext(needle);
int m = haystack.size(),n=needle.size();
int i=0,j=0;
while(i<m&&j<n)
{
if(haystack[i] == needle[j])
{
i++;j++;
}
else
{
if(j>0)
j = m_NextArr[j-1];
else
i++;
}
}
if(j==n)
return i-j;
return -1;
}
};