【算法】字符串匹配
1.经典的KMP算法
-
时间复杂度
O(n+m)：其中n为文本串s的长度，m为模式串p的长度。因为首先要遍历模式串求解部分匹配数组next，然后遍历文本串寻找匹配起始字符的下标。 -
空间复杂度为
O(m)：其中m为模式串的长度，用来存放next数组。
// kmp参考代码
// p: a b c d a b d a
// next: -1 0 0 0 0 1 2 0
// 可以直观理解为先求出最长前缀后缀公共长度，然后右移一位得到next的结果。
void get_next(std::string p, int *next)
{
int plen = p.size();
int i = 0;
int j = -1;
next[0] = -1;
while (i next(plen, 0);
get_next(p, next);
int i = 0;
int j = 0;
while (i 2.效率更高的Sunday算法
-
时间复杂度O(n)：其中n为文本串s的长度。因为只需要遍历文本串一遍，跳过的间隔相比kmp更大。
-
空间复杂度O(1)：只用到有限的几个指示变量。
// sunday
// 寻找next所指向的字符在模式串的最右侧出现的位置，然后更新next的值
void helper(std::string p, int plen, char ch, int *next)
{
int pos = plen-1;
for (int i=plen-1; i>=0; i--)
{
if (p[i]==ch) {
pos = i;
break;
}
}
// 模式串中不包含ch字符，则next向后再移动一位
if (pos==plen-1 && ch!=p[pos])
{
(*next)++;
} else {
// 如果找到了字符所在位置，则更新next的值
*next -= pos;
}
}
// aaabcdabaaabcdabdamns
// abcdabda
int sunday(std::string s, std::string p)
{
if (s.empty()) return -1;
if (p.empty()) return 0;
int slen = s.size();
int plen = p.size();
int i = 0;
int j = 0;
int next = 0;
while (i