KMP算法
前置知识
一个字符串的border指的是【既是它的前缀又是它的后缀的真子串】。
一个字符串的真子串不等于其自身。
对于字符串 s ，其前缀函数定义为
\pi(i)=\begin{cases}0&i=0\\max\{k|k<i,s[0...k-1]=s[i-(k-1)...i]\}&0<i<n\end{cases}
说人话： \pi(i) 即字符串s的border长度最大值。
在字符串匹配问题中，我们称被匹配的字符串为主串（通常更长），要尝试匹配的字符串为模式串（通常更短）。
前缀函数的模板
string s;
cin>>s;
int n = s.size();
s = " " + s;//1-based index
vector<int> pi(n+1);
for(int i = 2;i <= n;i++)
{
int len = pi[i - 1]; //len即除了当前扫到的末尾外最长的前缀长度
while(len > 0 && s[len + 1] != s[i])//s[len + 1] != s[i]表示：最长前缀的下一位与当前扫到的末尾不等同
len = pi[len];//把“最长前缀长度”缩短为次大值
if(s[len + 1] == s[i])//最长前缀的下一位与当前扫到的末尾等同，即没有参与过while循环
len++;//扩展1位成功了
pi[i] = len;//记录
}
KMP的模板
vector<int> pi;
string text,pattern;//text是主串，pattern是模式串
//...省略输入
vector<int> result; //存储模式串在主串中找到的开头下标（0-based）
/*if(pattern.empty() || text.size() < pattern.size())//显然不合法的情形
{
cout<<"Impossible";
return 0;
}*/
string combined = pattern + "#" + text;//0-based
//...省略求出combined的pi值过程
int plen = pattern.size(), clen = combined.size();
for(int i = plen + 1;i < clen;i++)//思考一下即知，索引plen + 1即指向combined中text的首个字符
if(pi[i] == plen)
result.push_back(i-2*plen);//*
//解释一下这个for循环：指针i在text部分右移，如果pi[i]等于plen，就说明此时的后缀就是pattern，即找到了一个完全一致的子串pattern。
注释*举例演示：
pattern = "ate"
text = "latex"
| combined | a | t | e | # | l | a | t | e | x |
|---|---|---|---|---|---|---|---|---|---|
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
i=7时找到pattern：ate。i-2*plen即7 - 2 * 3=1，而字符串text的下标1处正好为字符a。 |
鸣谢
感谢 @叶子宁 教练提供的 \pi(i) 函数求解代码。这对我的理解帮助巨大。
