`

hdu 2203 亲和串 (KMP算法)

阅读更多

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;
}

 

0
5
分享到:
评论

相关推荐

    hdu ACM代码 每种算法都有分类

    5. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法用于字符串匹配,Z算法、Manacher算法处理回文串问题。这些在文本处理、模式查找题目中必不可少。 6. **数据结构**:线段树、斐波那契堆、平衡树(AVL...

    ACM-HDU涉及了很多算法

    在ACM(国际大学生程序设计竞赛)中,HDU(杭州电子科技大学)的在线判题系统是许多参赛者磨炼算法技巧的重要平台。这个平台涵盖了众多的算法问题,旨在提升参赛者的编程能力和逻辑思维能力。以下是对标题和描述中...

    HDU算法讲解的PPT

    4. **字符串算法**:如KMP匹配、Rabin-Karp或Boyer-Moore算法,这些用于高效地处理字符串查询和匹配,对于文本处理和信息检索等领域尤为关键。 5. **数据结构**:如栈、队列、树(二叉树、AVL树、红黑树)、哈希表...

    HDU 算法 ACM课件

    8. **字符串算法**:KMP算法、Rabin-Karp算法、Manacher's Algorithm等,用于模式匹配和文本处理。 9. **数据结构**:栈、队列、链表、树(二叉树、平衡树如AVL和红黑树)、图等,良好的数据结构设计是高效算法的...

    samcat2021#ZXBlog#Hdu - 1711. Number Sequence以及KMP算法总结1

    next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前

    hdu.rar_hdu

    4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **数学应用**:组合数学、数论(质因数分解、模运算、欧几里得算法等)、概率论等。 6. **编码技巧**:IO优化(如scanf/printf代替cin/...

    zyq2652192993zyq#Advance-Algorithm#HDU-1711 Number Sequence(KMP算

    HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    KM匹配题集

    - **【HDU 2255】奔小康赚大钱**:可能需要利用KMP算法解决字符串匹配问题,寻找特定模式的出现次数。 - **【HDU 1533】Going Home**:同样是字符串匹配,可能需要求解最短的匹配长度或找出所有匹配位置。 - **【HDU...

    杭电ACMhdu1163

    3. **字符串处理**:杭电ACM中的题目可能涉及到字符串匹配(KMP算法、Boyer-Moore算法)、编码解码、模式查找等问题,熟悉字符串操作是必备技能。 4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论...

    ACM HDU题目分类

    贪心算法是一种常用的算法思想,在 ACM HDU 题目分类中,贪心算法也占据了一定的比例。例如,1009 贪心;1050 贪心;1052 贪心;1053 贪心,关于 Huffman 编码 等等。 数学题 数学题是 ACM HDU 题目分类中的一大类...

    acm课件 HDU 算法大全

    acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...

    hdu 300+ AC 代码

    在竞赛编程中,字符串问题可能涉及到KMP算法、Manacher's Algorithm(曼哈顿算法)或者Rabin-Karp滚动哈希等技术,用于高效地处理字符串的匹配和操作。 4. **动态规划(DP)**:动态规划是一种解决问题的系统方法,...

    hdu1010搜索算法

    杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题

    Hdu1000—2169部分代码

    6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等。 通过分析和理解这些代码,你可以提升自己的算法思维,学习如何高效地解决问题,这对于参加ACM竞赛或者日常的编程工作都非常有益。同时,也可以借鉴代码...

    ACM HDU

    6. **字符串处理**:模式匹配、KMP算法、Manacher's Algorithm等。 7. **模拟法**:直接按照题目描述进行程序模拟,解决一些逻辑性较强的问题。 学习和理解ACM HDU的题解,不仅可以提升编程能力,还能帮助我们理解...

    HDU最全ac代码

    3. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串操作和模式匹配技巧。 4. **数学知识**:组合数学、离散数学、数论等,许多竞赛题目需要运用到这些数学原理。 5. **优化技巧**:...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    Dijkstra算法解HDU1874

    **Dijkstra算法解HDU1874** Dijkstra算法是一种经典的图论算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出,主要用于解决单源最短路径问题。在这个问题中,我们需要从一个指定的起点(源节点)出发,找到...

    HDU+2000-2099+解题报告.zip

    5. **字符串处理**:包括KMP算法、Manacher's Algorithm等字符串匹配方法,以及Rabin-Karp、Rolling Hash等字符串搜索技术。解题报告会介绍这些方法的核心思想,以及如何利用它们解决实际问题。 6. **数学计算**:...

Global site tag (gtag.js) - Google Analytics