题意:
给出一个字符串,问是否存在这样的子串E使得字符串可以表示为EAEBE的形式,其中EAB的长度都为任意值,存在的话输出E的最长长度,否则输出-1
大致思路:
参考http://bbezxcy.iteye.com/blog/1378468 求字符串中存在多少子串使得其既是字符串的前缀也是字符串的后缀。这道题求出所有符合的后缀之后,再判断是否有子串可以成为中间的那个E,并选出长度最小的即可
#include<iostream> #include<cstring> #include<stack> #include<cstdio> #include<map> 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; } } map<int,int>mpp; int main(){ int i,j,k,tcs; scanf("%d",&tcs); while(tcs--){ scanf("%s",pat); lenp=strlen(pat); mpp.clear(); get_next(); j=next[lenp-1]; while(j!=-1){ mpp[j]=1; j=next[j]; } int res=-1; for(i=0;i<lenp;i++){ if(mpp[next[i]]!=0){ if(i-next[i]+1>next[i]&&lenp-i-1>=next[i]+1){ res=max(res,next[i]); } } } cout<<res+1<<endl; } return 0; }
相关推荐
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
6. **字符串处理**:模式匹配(KMP、Boyer-Moore、Rabin-Karp)、最长公共前后缀、编辑距离等。 7. **计算几何**:直线与圆的交点、点与多边形的关系、凸包问题等。 学习这些源代码可以提升编程能力,尤其是解决...
这些文件是针对“hdoj”(HDU Online Judge)在线编程竞赛平台的解题代码,涵盖了题目编号从1000到1050的若干题目。HDU Online Judge是一个用于训练和测试编程技能的系统,用户可以提交代码解决各种算法问题,并获取...
【HDOJ.zip_hduoj100题】是一个压缩包文件,包含了HDUOJ(杭州电子科技大学在线评测系统)的约100道编程练习题目及其源代码。这个资源对于想要提升编程技能,尤其是对算法和数据结构有深入学习需求的程序员来说,是...
【HDOJ暑期多校联赛第三场】是2013年举办的一场面向广大编程爱好者的在线竞赛,由IOI(国际奥林匹克信息学竞赛)的冠军CLJ设计题目,旨在提升参赛者的信息学和算法解决能力。这次比赛涵盖了丰富的编程和算法知识点,...
这些文件是关于ACM(国际大学生程序设计竞赛,简称ICPC)比赛的解题报告,主要涵盖杭电(杭州电子科技大学)在线评测系统HDOJ(HDU Online Judge)中的题目2051到2099。在ACM竞赛中,参赛队伍需要解决一系列算法问题...
3. **字符串处理**:在文本处理和模式匹配问题中,字符串操作是常见的,如KMP算法、Boyer-Moore算法等。 4. **数学应用**:包括数论、组合数学、线性代数、概率统计等,很多问题需要用到数学思维来简化问题并找到...
9. **字符串处理**:KMP算法、Manacher's Algorithm等。 在"ACM_HDU-master"中,我们可以期待看到如何运用这些知识去解决具体问题的实例。每个子文件可能对应一个或多个HDU的题目,包含了解题报告、C++代码实现和...
同时,由于是杭州电子科技大学的内部培训资料,其中可能还包含了历年杭电(HDOJ,杭州电子工业学院在线评测系统)的题目解析和解题思路,这对于熟悉HDOJ题库和提升解题能力非常有帮助。 总的来说,《杭电2010ACM...
"poj pku字符串题目推荐及解题报告.doc"专注于字符串处理,这是编程竞赛中常见的一类问题,包括模式匹配、KMP算法、Manacher's Algorithm等。 7. **ACM应掌握的知识点**: "ACM应掌握的知识点.doc"可能是对参加...
HDOJ LeetCode 程序员面试金典 剑指OFFER PAT 甲级 乙级 ACWing 算法基础班 快排 归并 二分 高精度 前缀和差分 双指针 位运算 离散化 区间合并 单链表 双链表 栈 队列 单调栈 单调队列 KMP Tire 并查集 堆 哈希表 ...
6. **字符串处理**:KMP匹配、Manacher算法、Rabin-Karp滚动哈希等。 7. **数据结构**:栈、队列、链表、树、图、哈希表等。 8. **数学问题**:数论、组合数学、概率统计等。 总的来说,"ACM离线题库(1200道)" 是...
PPT可能还会推荐一些在线编程平台,如LeetCode、HDOJ(杭电在线评测系统)等,供学习者进行实战训练。 最后,PPT可能会提到团队合作和心理素质的培养,因为ACM竞赛不仅是技术的比拼,也是团队协作能力和心理承受力...
6. 字符串处理:模式匹配(KMP、Boyer-Moore)、字符串函数(Rabin-Karp、Z-Algorithm)等技术在文本处理问题中不可或缺。 7. 动态规划优化:记忆化搜索、状态压缩、滚动数组等技巧可以显著提高代码效率。 三、实战...
熟练掌握这些基础知识后,你需要通过不断练习,参与在线判题平台(如LeetCode、Codeforces、HDOJ等)的题目,提高解决问题的能力。同时,学习他人的解题思路,了解如何在限制时间内构思、编写和调试代码,也是提升...
随着ACM竞赛难度的提升,需要掌握更高级的算法,如字符串匹配(KMP、Boyer-Moore、Rabin-Karp等)、网络流、数学建模(组合数学、线性代数、数论)、最优化问题(线性规划、分支定界法)等。这些算法往往能解决复杂...
【文件名称】:“hdoj离线题库(更新至2223).CHM”是一个帮助文件格式,通常包含组织良好的索引和内容,便于用户查找和阅读题目。CHM文件是Microsoft的 Compiled HTML Help 格式,它将HTML文档集合打包成一个可搜索...
- **题库选择**:选择合适的在线平台进行训练非常重要,如Codeforces、HDOJ、UVA等,这些平台提供了丰富的题目供选手练习。 - **解题策略**:学会高效地分析问题,明确题目要求,确定使用的算法和数据结构。在编码...