大致题意:
给出一个字符串str,求出str中存在多少子串,使得这些子串既是str的前缀,又是str的后缀。从小到大依次输出这些子串的长度。
大致思路:
如左图,假设黑色线来代表字符串str,其长度是len,红色线的长度代表next[len],根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同(也就是两条线所对应的位置)。我们再求出next[len]位置处的next值,也就是图中蓝线对应的长度。同样可以得到两个蓝线对应的子串肯定完全相同,又由于第二段蓝线属于左侧红线的后缀,所以又能得到它肯定也是整个字符串的后缀。
所以对于这道题,求出len处的next值,并递归的向下求出所有的next值,得到的就是答案。
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
stack<int>ans;
int main(){
while(scanf("%s",pat)!=EOF){
lenp=strlen(pat);
get_next();
int j=next[lenp-1];
while(j!=-1){
ans.push(j);
j=next[j];
}
while(!ans.empty()){
cout<<ans.top()+1<<" ";
ans.pop();
}cout<<lenp<<endl;
}
return 0;
}
分享到:
相关推荐
pku acm 2752 Seek the Name, Seek the Fame代码 kmp算法。解题报告:http://blog.csdn.net/china8848
- POJ 1961、POJ 2406:KMP算法的应用。 ### 其他问题 #### 贪心算法 - **题目示例**: - POJ 3411、POJ 1724:贪心策略的选择与应用。 #### 二分查找 - **题目示例**: - POJ 3373、POJ 1691:二分查找技术的...
《KMP算法在POJ题目中的应用》 KMP(Knuth-Morris-Pratt)算法,是一种在字符串中寻找子串的搜索算法,由Donald Knuth、Vaughan Pratt和James H. Morris三位学者于1970年代提出。在编程竞赛如POJ(Problemset On...
- (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...
* KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 * 记忆化搜索:例如 poj3373、poj1691。 5. 动态规划: * 较为复杂的动态规划:...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
D-KMP体系结构-官方样本这是D-KMP架构的官方示例,展示了一个适用于Android和iOS的简单主/详细应用程序。 有关D-KMP体系结构的更多信息,请阅读相关的。D-KMP体系结构的主要功能: 它使用最新的声明性UI工具包:适用...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
《KMP-Expander:CSV格式的Mario Kart 7赛道编辑工具详解》 在电子游戏领域,特别是赛车游戏,Mario Kart 7凭借其丰富的赛道设计和竞技性深受玩家喜爱。为了满足玩家对自定义赛道的需求,开发人员和爱好者们创造了...
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...
**热-KMP算法:字符串匹配的高效利器** KMP(Knuth-Morris-Pratt)算法是一种在文本中高效地查找子串出现位置的字符串匹配算法。由唐纳德·克努斯、维克托·莫里斯和弗兰克·普拉特在1970年提出。该算法避免了在...
KMP(Knuth-Morris-Pratt)算法是由D.E. Knuth、V. Morris和J.H. Pratt三位学者在1970年提出的一种高效的字符串匹配算法,它主要用于解决在一个大文本串中查找是否存在一个特定模式串的问题。KMP算法的效率在于它...
5. **字符串匹配**:如KMP算法(poj1961, poj2406)。 ### 十三、进阶算法 1. **组合优化**:如割平面法、分支定界法等(poj3411, poj1724)。 2. **近似算法**:解决NP难问题时的近似求解方法(poj3373, poj1691...
D-KMP架构Daniele Baroncelli建议的D-KMP体系结构的试用示例,位于: ://danielebaroncelli.medium.com/the-future-of-apps-declarative-uis-with-kotlin-multiplatform-d-kmp-part-1 它:声明性UI(Jetpack编写)...
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
6. **KMP算法**(如poj1961, poj2406):高效的字符串匹配算法,适用于文本检索、模式识别等领域。 #### 优化技巧 1. **代码优化**(如poj3096, poj3007):包括循环展开、条件判断优化等,提高代码执行效率。 2. ...
2. **POJ1790**:可能涉及字符串的模式匹配,如KMP算法或Boyer-Moore算法,用于在一个字符串中寻找另一个字符串的出现位置。 3. **POJ1951**:可能与字符串的排序有关,比如可以运用Manacher's Algorithm解决最长...
* KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、POJ3034 * 记录状态的动态规划:POJ3254、...
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...