http://acm.hdu.edu.cn/showproblem.php?pid=2203
解题报告:由题目:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。移位循环,最多多循环循环一个s1的长度,因此我们可以把s1中的前n-1位直接添加到s1的后面,
如s1=AABCD,可以变为s1=AABCDAABC,这样就包含了所有的情况,然后循环遍历即可。
#include<cstdio> #include<cstring> using namespace std; const int MAX = 100000 + 5; char a[2*MAX],b[MAX]; int next[MAX],len1,len2; void get_next() { int i,j=-1; next[0]=-1; for(int i=1;i<=len2;i++) { while(j>-1&&b[j+1]!=b[i]) { j=next[j]; } if(b[j+1]==b[i]) j++; next[i]=j; } } bool KMP() { get_next(); int i=0,j=-1; for(int i=0;i<2*len1-1;i++) { while(j>-1&&b[j+1]!=a[i]) j=next[j]; if(b[j+1]==a[i]) j++; if(j==len2-1) return true; } return false; } int main() { while(scanf("%s %s",a,b)!=EOF) { len1=strlen(a); for(int j=0;j<len1-1;j++) a[j+len1]=a[j]; len2=strlen(b); if(KMP()) printf("yes\n"); else printf("no\n"); } return 0; }
相关推荐
5. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法用于字符串匹配,Z算法、Manacher算法处理回文串问题。这些在文本处理、模式查找题目中必不可少。 6. **数据结构**:线段树、斐波那契堆、平衡树(AVL...
在ACM(国际大学生程序设计竞赛)中,HDU(杭州电子科技大学)的在线判题系统是许多参赛者磨炼算法技巧的重要平台。这个平台涵盖了众多的算法问题,旨在提升参赛者的编程能力和逻辑思维能力。以下是对标题和描述中...
4. **字符串算法**:如KMP匹配、Rabin-Karp或Boyer-Moore算法,这些用于高效地处理字符串查询和匹配,对于文本处理和信息检索等领域尤为关键。 5. **数据结构**:如栈、队列、树(二叉树、AVL树、红黑树)、哈希表...
8. **字符串算法**:KMP算法、Rabin-Karp算法、Manacher's Algorithm等,用于模式匹配和文本处理。 9. **数据结构**:栈、队列、链表、树(二叉树、平衡树如AVL和红黑树)、图等,良好的数据结构设计是高效算法的...
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **数学应用**:组合数学、数论(质因数分解、模运算、欧几里得算法等)、概率论等。 6. **编码技巧**:IO优化(如scanf/printf代替cin/...
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
- **【HDU 2255】奔小康赚大钱**:可能需要利用KMP算法解决字符串匹配问题,寻找特定模式的出现次数。 - **【HDU 1533】Going Home**:同样是字符串匹配,可能需要求解最短的匹配长度或找出所有匹配位置。 - **【HDU...
3. **字符串处理**:杭电ACM中的题目可能涉及到字符串匹配(KMP算法、Boyer-Moore算法)、编码解码、模式查找等问题,熟悉字符串操作是必备技能。 4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论...
贪心算法是一种常用的算法思想,在 ACM HDU 题目分类中,贪心算法也占据了一定的比例。例如,1009 贪心;1050 贪心;1052 贪心;1053 贪心,关于 Huffman 编码 等等。 数学题 数学题是 ACM HDU 题目分类中的一大类...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
在竞赛编程中,字符串问题可能涉及到KMP算法、Manacher's Algorithm(曼哈顿算法)或者Rabin-Karp滚动哈希等技术,用于高效地处理字符串的匹配和操作。 4. **动态规划(DP)**:动态规划是一种解决问题的系统方法,...
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等。 通过分析和理解这些代码,你可以提升自己的算法思维,学习如何高效地解决问题,这对于参加ACM竞赛或者日常的编程工作都非常有益。同时,也可以借鉴代码...
6. **字符串处理**:模式匹配、KMP算法、Manacher's Algorithm等。 7. **模拟法**:直接按照题目描述进行程序模拟,解决一些逻辑性较强的问题。 学习和理解ACM HDU的题解,不仅可以提升编程能力,还能帮助我们理解...
3. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串操作和模式匹配技巧。 4. **数学知识**:组合数学、离散数学、数论等,许多竞赛题目需要运用到这些数学原理。 5. **优化技巧**:...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
**Dijkstra算法解HDU1874** Dijkstra算法是一种经典的图论算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于解决单源最短路径问题。在这个问题中,我们需要从一个指定的起点(源节点)出发,找到...
5. **字符串处理**:包括KMP算法、Manacher's Algorithm等字符串匹配方法,以及Rabin-Karp、Rolling Hash等字符串搜索技术。解题报告会介绍这些方法的核心思想,以及如何利用它们解决实际问题。 6. **数学计算**:...