作者推荐
本文涉及的基础知识点
LeetCode100207. 找出数组中的美丽下标 II
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：
0 <= i <= s.length - a.length
s[i…(i + a.length - 1)] == a
存在下标 j 使得：
0 <= j <= s.length - b.length
s[j…(j + b.length - 1)] == b
|j - i| <= k
以数组形式按 从小到大排序 返回美丽下标。
示例 1：
输入：s = “isawsquirrelnearmysquirrelhouseohmy”, a = “my”, b = “squirrel”, k = 15
输出：[16,33]
解释：存在 2 个美丽下标：[16,33]。
- 下标 16 是美丽下标，因为 s[16…17] == “my” ，且存在下标 4 ，满足 s[4…11] == “squirrel” 且 |16 - 4| <= 15 。
- 下标 33 是美丽下标，因为 s[33…34] == “my” ，且存在下标 18 ，满足 s[18…25] == “squirrel” 且 |33 - 18| <= 15 。
因此返回 [16,33] 作为结果。
示例 2：
输入：s = “abcd”, a = “a”, b = “a”, k = 4
输出：[0]
解释：存在 1 个美丽下标：[0]。 - 下标 0 是美丽下标，因为 s[0…0] == “a” ，且存在下标 0 ，满足 s[0…0] == “a” 且 |0 - 0| <= 4 。
因此返回 [0] 作为结果。
提示：
1 <= k <= s.length <= 5 * 105
1 <= a.length, b.length <= 5 * 105
s、a、和 b 只包含小写英文字母。
KMP
KMP类的 vector m_vSameLen;//m_vSame[i]记录 s[i…]和t[0…]最长公共前缀，增加可调试性
枚举(s,a)的下标看m_vSameLen[i] 是否等于a.length。
(s,b)类似。将符合条件的下标放到bindex中，由于是升序，所以可以用二分查找。看是否存在[i-k,i+k]的下标。
代码
封装类
class KMP { public: virtual int Find(const string& s, const string& t) { CalLen(t); m_vSameLen.assign(s.length(), 0); for (int i1 = 0, j = 0; i1 < s.length(); ) { for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++); //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等 m_vSameLen[i1] = j; //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2) if (0 == j) { i1++; continue; } const int i2 = i1 + j; j = m_vLen[j - 1]; i1 = i2 - j;//i2不变 } for (int i = 0; i < m_vSameLen.size(); i++) {//多余代码是为了增加可测试性 if (t.length() == m_vSameLen[i]) { return i; } } return -1; } vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 protected: void CalLen(const string& str) { m_vLen.resize(str.length()); for (int i = 1; i < str.length(); i++) { int next = m_vLen[i - 1]; while (str[next] != str[i]) { if (0 == next) { break; } next = m_vLen[0]; } m_vLen[i] = next + (str[next] == str[i]); } } int m_c; vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 };
核心代码
class Solution { public: vector<int> beautifulIndices(string s, string a, string b, int k) { KMP kmpa, kmpb; kmpa.Find(s, a); kmpb.Find(s, b); vector<int> bindex; for (int i = 0; i < kmpb.m_vSameLen.size(); i++) { if (kmpb.m_vSameLen[i] == b.length()) { bindex.emplace_back(i); } } vector<int> vRet; for (int i = 0; i < kmpa.m_vSameLen.size(); i++) { if (kmpa.m_vSameLen[i] == a.length()) { auto it1 = std::lower_bound(bindex.begin(), bindex.end(), i - k); auto it2 = std::upper_bound(bindex.begin(), bindex.end(), i + k); if (it2 - it1 > 0) { vRet.emplace_back(i); } } } return vRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string a,b,s; int k; { Solution sln; s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15; auto res = sln.beautifulIndices(s, a, b, k); Assert(vector<int>{16, 33}, res); } { Solution sln; s = "abcd", a = "a", b = "a", k = 4; auto res = sln.beautifulIndices(s, a, b, k); Assert(vector<int>{0}, res); } }
