题目链接:hdu 4300 Clairewd’s message
题目大意:题目意思比较难懂,给出两个字符串,第一个字符串为编码规则,比如说样例1,q位于第一个位置,表示说q的编码是a。然后给出另一个字符串s,要求添加尽量少得字符,使得f可以被分成两部分f1+f2, 然后f1编码后等于f2,然后注意给出的f串为编码串,并非原串。
解题思路:首先先将f串转换成原串s,然后求出jump数组,去和f匹配,对于匹配的最后一项值p(即为最长匹配后缀),n-p即是我们要求的f1的长度(但是这里要注意n-p 不能小于p,因为分成两部分后不能说有公共的部分存在,所以p = jump[p])
#include <stdio.h>
#include <string.h>
const int N = 1e5+5;
int n, jump[N];
char t[30], v[30], s[N], f[N];
void getJump () {
int p = 0;
for (int i = 2; i <= n; i++) {
while (p > 0 && s[p+1] != s[i])
p = jump[p];
if (s[p+1] == s[i])
p++;
jump[i] = p;
}
}
int KMP () {
int p = 0;
for (int i = 1; i <= n; i++) {
while (p > 0 && s[p+1] != f[i])
p = jump[p];
if (s[p+1] == f[i])
p++;
if (p == n)
p = jump[p];
}
while (n - p < p)
p = jump[p];
return p;
}
void init () {
scanf("%s%s", t, f+1);
n = strlen (f+1);
for (int i = 0; i < 26; i++)
v[t[i]-'a'] = i + 'a';
for (int i = 1; i <= n; i++)
s[i] = v[f[i]-'a'];
s[n+1] = '\0';
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init ();
getJump ();
int k = n - KMP ();
for (int i = 1; i <= k; i++)
printf("%c", f[i]);
for (int i = 1; i <= k; i++)
printf("%c", v[f[i]-'a']);
printf("\n");
}
return 0;
}
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **数学应用**:组合数学、数论(质因数分解、模运算、欧几里得算法等)、概率论等。 6. **编码技巧**:IO优化(如scanf/printf代替cin/...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
6. **字符串处理**:模式匹配、KMP算法、Manacher's Algorithm等。 7. **模拟法**:直接按照题目描述进行程序模拟,解决一些逻辑性较强的问题。 学习和理解ACM HDU的题解,不仅可以提升编程能力,还能帮助我们理解...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
3. **字符串处理**:杭电ACM中的题目可能涉及到字符串匹配(KMP算法、Boyer-Moore算法)、编码解码、模式查找等问题,熟悉字符串操作是必备技能。 4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
3. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串操作和模式匹配技巧。 4. **数学知识**:组合数学、离散数学、数论等,许多竞赛题目需要运用到这些数学原理。 5. **优化技巧**:...
对于特定问题,比如最大子序列和、最小覆盖子集等,需要掌握特定算法,如Kadane's algorithm或Dijkstra's algorithm。 四、数学基础:开启解题新维度 数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
hdu2101AC代码
在竞赛编程中,字符串问题可能涉及到KMP算法、Manacher's Algorithm(曼哈顿算法)或者Rabin-Karp滚动哈希等技术,用于高效地处理字符串的匹配和操作。 4. **动态规划(DP)**:动态规划是一种解决问题的系统方法,...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU-ACM源代码是针对国际大学生程序设计竞赛(ICPC,International Collegiate Programming Contest)中的题目,由参赛者或爱好者编写的解决方案集合。这个压缩包包含上百个源代码,涉及了各种算法和编程技巧,是...