网站开发部门结构,网站开发图片存哪里,长春头条新闻今天,做阀门网站电话大家好#xff0c;今天是2025年8月31日#xff0c;上一期我给大家分享了 KMP 算法的相关知识#xff0c;今天我来带领大家学习4道 KMP 相关的算法题。
在学习算法题之前#xff0c;还是希望大家能够要先学会 KMP 算法#xff08;可以参考这篇文章#xff1a;KMP 算法今天是2025年8月31日上一期我给大家分享了 KMP 算法的相关知识今天我来带领大家学习4道 KMP 相关的算法题。
在学习算法题之前还是希望大家能够要先学会 KMP 算法可以参考这篇文章KMP 算法
当然如果你是高手的话也可以自己先尝试一下解决下面的四道问题检验一下你的 KMP 算法的掌握程度。
那么废话不多收我们开启今天的学习
题目一剪花布条
题目链接剪花布条
【题目描述】 【算法原理】
这道题一眼就可以看出是字符串匹配的问题暴力解法当然是拿着模式串去主串的每一个位置依次进行匹配时间复杂度较高但是这道题目数据范围比较小应该也是可以通过~~
这种字符串匹配的问题我们可以尝试使用 KMP 算法进行解决。
但不同于 KMP 算法模板题的是这道题目找到所有匹配的位置之后还要从左到右进行判断筛选不能重叠。这个只需要额外判断匹配位置之间的距离是否大于模式串的长度就可以了。
注意可见的 ASCII 字符是包括 ‘#’ 的因此我们用 ‘ ’空格来链接模式串和主串。
【代码实现】
#include iostreamusing namespace std;const int N 2010; // 注意要开成两倍 string s, t;
int n, m;
int pi[N];int main()
{while(cin s t){int ret 0; n s.size(); m t.size();s t s;for(int i 2; i m n 1; i){int j pi[i - 1];while(j s[i] ! s[j 1]) j pi[j];if(s[i] s[j 1]) j;pi[i] j;}for(int i m 1; i m n 1; i){if(pi[i] m){ret;i m - 1; // 出去以后还会 一次 // 防重叠 }}cout ret endl;}return 0;
} 题目二Seek the Name
题目链接Seek the Name
【题目描述】 【算法原理】
前缀函数的小用途~~
border 的 border 还是 border
题目要求求出字符串所有 border 的长度我们可以先求出最长的 border 的长度再依次去找短的 border。这道题目就是一个简单的求前缀函数的问题~~
用数组存储所有 border 的长度最后再逆序输出。有一种数组模拟栈的感觉
最后不要忘记输出整个字符串的长度~~求 border 不会考虑但是本题是要考虑的。
【代码实现】
#include iostreamusing namespace std;const int N 4e5 10;string s;
int n, pi[N];
int ret[N], top;int main()
{while(cin s){top 0;n s.size();s s;for(int i 2; i n; i){int j pi[i - 1];while(j s[i] ! s[j 1]) j pi[j];if(s[i] s[j 1]) j;pi[i] j;}for(int i pi[n]; i; i pi[i]) ret[top] i;for(int i top; i 1; i--) cout ret[i] ;cout n endl;}return 0;
} 题目三ABB
题目链接 ABB
【题目描述】 【算法原理】
对于回文串相关的问题可以使用 malache 算法来解决但是我们这个专题是 KMP因此我们尝试使用 KMP 算法来解决这个问题。
题目转化这道题实质上是求给定字符串的最长回文后缀的长度 lenn - len 就是最终结果。
因为题目要求你只能从字符串的末端去补充字符所以回文后缀的长度越长你要补充的字符数量就越少。
所以我们只需要解决求出一个字符串的最长回文后缀的长度就可以了~~
如何解决这个问题呢
我们发现如果将回文串逆序应该和原始的字符串相同。因此我们可以将字符串逆序之后拼接到原始字符串的前面在中间加一个 ‘#’ 连接。 接下来我们只需要求出新字符串最长的 border 长度 pi再用 n - pi 就解决了。
【代码实现】
#include iostream
#include algorithmusing namespace std;const int N 8e5 10; // 开两倍 string s, t;
int n;
int pi[N];int main()
{cin n s;t s;reverse(t.begin(), t.end());s t # s;for(int i 2; i n n 1; i){int j pi[i - 1];while(j s[i] ! s[j 1]) j pi[j];if(s[i] s[j 1]) j;pi[i] j;}cout n - pi[n n 1] endl;return 0;
}
题目四Censoring S
题目链接Censoring S
【题目描述】 【算法原理】
KMP 算法 栈存下标
对于这种类似”消消乐“的玩法我们很容易想到 “栈” 这样的一个数据结构。 对于之前求前缀函数的模板我们优先考虑使用【1i - 1】的 border 来更新 【1i】的 border
但是这道题目涉及消除的操作因此我们不能使用【1i - 1】的 border 来更新 【1i】的 border有可能前面的字符都消没了
而是使用栈顶下标的元素来更新【1i】的 border。 【代码实现】
#include iostreamusing namespace std;const int N 2e6 10;string s, t;
int n, m, pi[N];
int st[N], top; // 用数组模拟栈 int main()
{cin s t;n s.size(), m t.size();s t s;// pi[1] 0;st[top] 1;for(int i 2; i n m 1; i){int j pi[st[top]];while(j s[i] ! s[j 1]) j pi[j];if(s[i] s[j 1]) j;pi[i] j;st[top] i;if(j m){for(int k 0; k m; k) top--;}}for(int i m 2; i top; i) cout s[st[i]];return 0;
}好的今天的分享到这里就结束了谢谢大家
