KMP 算法模版
给你一个模式串 T 与一个目标串 S，我们要快速找到 T 在 S 中的所有出现，复杂度为 $O(|S| + |T|)$。
需要额外说明的是这里的代码对于 Next 数组多算了一位，相当于给原本的模式串 T 后增加了一个无法匹配的字符。在匹配的过程中一旦要比较模式串无法匹配的字符，那么就说明匹配成功了，然后本次比较一定失配，跳 Next 数组。
C++ 代码
C++ 的代码封装在一个 NameSpace 中。build 函数可以计算出模式串 pattern 的 Next 数组；match 函数求出 pattern 在 text 中的所有出现位置，并返回那些开始位置。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
namespace KMP{ vector<int> next; void build(const string &pattern){ int n = pattern.length(); next.resize(n + 1); for (int i = 0, j = next[0] = -1; i < n; next[++i] = ++j){ while(~j && pattern[j] != pattern[i]) j = next[j]; } } vector<int> match(const string &pattern, const string &text){ vector<int> res; int n = pattern.length(), m = text.length(); build(pattern); for (int i = 0, j = 0; i < m; ++i){ while(j > 0 && text[i] != pattern[j]) j = next[j]; if (text[i] == pattern[j]) ++j; if (j == n) res.push_back(i - n + 1), j = next[j]; } return res; } }; |
Python 代码
Python 代码封装在一个类中，调用构造函数传入模式串 T，初始化模式串 T 的 Next 数组。传入目标串 S 调用类的 match 函数，可以返回模式串 T 的在目标串 S 中的所有出现的开始位置。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class KMP: def __init__(self, T: str): self.T, self.n = T, len(T) self.next = [0] * (self.n + 1) self.next[0], j = -1, -1 for i in range(self.n): while j >= 0 and T[i] != T[j]: j = self.next[j] j += 1 self.next[i + 1] = j def match(self, S: str): m, j, res = len(S), 0, [] for i in range(m): while j > 0 and S[i] != self.T[j]: j = self.next[j] if S[i] == self.T[j]: j += 1 if j == self.n: res.append(i - self.n + 1) j = self.next[j] return res |
还没有任何评论，你来说两句吧!