当前位置：首页 > news >正文

字符串KMP算法

news 2026/3/26 19:31:34

反转字符串中的单词 (leetcode.151)

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

这题可以参考移除元素的思路，我们再进行移除数组中的元素的时候，通过快慢指针，来实现目标数的移除，这里我们依旧可以作为参考

首先移除字符串中多余的空格，其次，整个字符串反转，最后将每个单词反转。

那么移除空格就可以考虑使用快慢指针的方式

int slow = 0;
for(int fast = 0; fast < s.size(); ++fast){if(s[fast] != ' '){s[slow++] = s[fast];}
}

这样虽然实现了移除空格的操作，但是这却有个问题，"a big apple",执行完后会变成abigapple,它会把单词间的正常空格也删了，这就不对了。哪如何改进呢？我们可以这样，快指针遍历到的字母如果不是空格，那么就是单词的第一个字符，也就是单词的首个字母。

int slow = 0;
for(int fast = 0; fast < s.size(); ++fast){if(s[fast] != ' '){ // 只判断得到单词的首个字母if(slow == 0) s[slow++] = ' ';  // 如果是第一个单词，那么就不加空格while(fast < s.size() && s[fast] != ' '){ // 上面得到了单词首个字母,继续后找，找到空格就说明单词结束s[slow++] = s[fast++];}}
}

这样我们确实将空格问题处理了，之后就可以得到新字符，反转，然后单独反转单词就完成了

class Solution {
public:void reverse(string& s, int i, int j){for(; i < j; ++i,--j){std::swap(s[i], s[j]);}}string reverseWords(string s) {// 移除所有空格元素int slow = 0;for(int fast = 0; fast < s.size(); ++fast){if(s[fast] != ' '){  // 只负责找到单词的开头if(slow != 0) s[slow++] = ' '; // 不是首个单词while(fast < s.size() && s[fast] != ' '){s[slow] = s[fast];++slow;++fast;}}}s.resize(slow); // 截断后面的// 先反转整体reverse(s, 0, s.size()-1);// 再反转单词int start = 0;for(int i = 0; i <= s.size(); ++i){if(i == s.size() || s[i] == ' '){reverse(s,start, i-1);start = i+1;}}return s;}
};

找匹配字符串（leetcode.28）

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();for(int i = 0; i <= n-m; i++){int j = i, k = 0;while(k < m && haystack[j] == needle[k]){++k;++j;}if(k==m) return i;}return -1;}
};

首先是暴力解法，简单来说就是一个一个遍历haystack，然后和needle比对，失败后继续遍历，又重新开始needle比对，所以时间复杂度O((n-m) * m)

KMP解法

重点讲讲kmp算法，本题就是如何快速在「原字符串」中找到「匹配字符串」。

KMP 能够在 O(m+n) 复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。

这里我们先不讲解相关的算法，我们先讲一个重要的前置知识，前缀函数。

这个定义是这样的：一个长度为n的字符串s，其前缀函数被定义为一个长度为n的数组$\pi$，$\pi[i]$的定义是有相等的、最长的真前缀与真后缀。

举个例子：

对于字符串 abcabcd，

𝜋[0] =0 $\pi[0]=0$ ，因为 a 没有真前缀和真后缀，根据规定为 0

𝜋[1] =0 $\pi[1]=0$ ，因为 ab 无相等的真前缀和真后缀

𝜋[2] =0 $\pi[2]=0$ ，因为 abc 无相等的真前缀和真后缀

𝜋[3] =1 $\pi[3]=1$ ，因为 abca 只有一对相等的真前缀和真后缀：a，长度为 1

𝜋[4] =2 $\pi[4]=2$ ，因为 abcab 相等的真前缀和真后缀只有 ab，长度为 2

𝜋[5] =3 $\pi[5]=3$ ，因为 abcabc 相等的真前缀和真后缀只有 abc，长度为 3

𝜋[6] =0 $\pi[6]=0$ ，因为 abcabcd 无相等的真前缀和真后缀

同理可以计算字符串 aabaaab 的前缀函数为 [0,1,0,1,2,2,3]．

那么这个前缀函数如何求解？

或许可以通过暴力求解，比如求$\pi[5]$，那么就可以得出真前后缀长度1~5，逐一比较，求$\pi[n]$的复杂度就O(n2)了。还有很大的进步空间

递推法求前缀函数

已知 π[0]~π[i-1]，求 π[i] 时，先看 s[i] 是否等于 s[π[i-1]]：

如果相等 → π[i] = π[i-1] + 1；
如果不相等 → 回退到 π[π[i-1]-1]，再比较，直到回退到 0；
如果回退到 0 还不相等 → π[i] = 0。

其实这段我看的时候有点难以理解，我这猪脑早就不知道过载多少遍了。

还是用个例子，这里如果求 π[i+1]，这里 π[i]=3，如果字符串s[i+1] = s[π[i]] = s[3]，那太好了， π[i+1] = π[i] + 1 。

但是大多数时候s[i+1] != s[π[i]]，那如何进行跳转？

不匹配啊，怎么办！怎么办！怎么办！先别慌，问题是一定要解决的，先梳理情况，现在已知的信息是s[0...i]的最长前缀函数不能进行匹配了，那么就找第二长度的次于π[i]的j进行比较，使得满足s[0...j-1] = s[i-j+1...i]

如果找到了j，那么比较s[j]、s[i+1]，不行就找第三长的，直到 j 为0，那么π[i+1] = 0了

这里第二长的是 ac，就有

这里可得一个性质，因为s[0...π[i]-1] = s[i-π[i]+1...i] （s[0..3] = s[i-3...i]）,也就是acac = acac，这个是从s[0...i]最长的也就是π[i]，第二长的 j = 2 可以得到：

s[0...j-1] = s[i-j+1...i] = s[π[i]-j...π[i]-1]↓			↓				↓
s[0 1]  = s[i-1 i]		= 	s[π[i]-2 π[i]-1]ac  = ac = s[4-2 4-1]

还是有点抽象？没关系，因为这里我也看不懂

π[i] = 4，说明黄色框内的前后缀一样，而红框当然也一样，没问题吧，红框是黄框子类，当然一样了，那么蓝色是第二长度的前缀函数，蓝色框一样，这不就说明蓝色框 = 红色框，不就是说我找第二长度的 j，只要找左边黄色框的前缀函数，也就是j = s[0] ~ s[π[i]-1] = s[0]~s[3] = π[3] acac的前缀函数 ，j很明显是2，那第三长的是不是就有$k = \pi[\pi[j]-1]$，第三长是π[0] = 0,注意到有这样的一个状态转移方程：(吓哭了)

$j^{(n)} = \pi[j^{(n-1)}-1]$

最后，其实代码是很简单的

vector<int> pi(s.size());
for(int i = 1; i < s.size(); i++){int len = pi[i-1]; // 前一个while(len != 0 && s[i] != s[len]){ // 注意下标len = pi[len-1]; }if(s[i] == s[len]){pi[i] = len+1;}
}

花了这么多时间，求了个前缀函数，这道题可以解吗？

可以的，直接解

class Solution {
public:int strStr(string haystack, string needle) {string s = needle + '#' + haystack;vector<int> pi(s.size());for(int i = 1; i < s.size(); i++){int len = pi[i-1]; // 前一个while(len != 0 && s[i] != s[len]){ // 注意下标len = pi[len-1]; }if(s[i] == s[len]){pi[i] = len+1;if(pi[i] == needle.size()) {// 返回haystack的匹配第一个 return i - needle.size() * 2;}}}return -1;}
};