做取名的网站很赚钱吗,为什么不用h5做网站,青岛网签查询系统,合伙做网站怎么分配股权作者推荐
【矩阵快速幂】封装类及测试用例及样例
本文涉及的基础知识点
二分查找算法合集
LeetCode100207. 找出数组中的美丽下标 II
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。 如果下标 i 满足以下条件#xff0c;则认为它是一个 美丽下标…作者推荐
【矩阵快速幂】封装类及测试用例及样例
本文涉及的基础知识点
二分查找算法合集
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,ik]的下标。
代码
封装类
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;}vectorint 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;vectorint m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀
};核心代码
class Solution {
public:vectorint beautifulIndices(string s, string a, string b, int k) {KMP kmpa, kmpb;kmpa.Find(s, a);kmpb.Find(s, b);vectorint bindex;for (int i 0; i kmpb.m_vSameLen.size(); i){if (kmpb.m_vSameLen[i] b.length()){bindex.emplace_back(i);}}vectorint 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;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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(vectorint{16, 33}, res);}{Solution sln;s abcd, a a, b a, k 4;auto res sln.beautifulIndices(s, a, b, k);Assert(vectorint{0}, res);}
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
