【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II

作者推荐

【矩阵快速幂】封装类及测试用例及样例

本文涉及的基础知识点

二分查找算法合集

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 * 10⁵
1 <= a.length, b.length <= 5 * 10⁵
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);
	}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛