HDU 4300 Clairewd’s message (next函数的应用)
2024-08-26 04:23:40
题意:给你一个明文对密文的字母表,在给你一段截获信息,截获信息前半段是密文,后半段是明文,但不清楚它们的分界点在哪里,密文一定是完整的,明文可能是残缺的,求完整的信息串(即完整的密文+明文串)。
题解:KMP next函数的应用。
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ; char table[];
char extable[];
char ori[MAXN];
char aft[MAXN];
int next[MAXN];
int len; void init()
{
for ( int i = ; i < ; ++i )
extable[ table[i]-'a' ] = 'a' + i; len = strlen(ori);
for ( int i = ; i < len/; ++i )
aft[i] = ori[i]; for ( int i = len/; i < len; ++i )
aft[i] = table[ ori[i] - 'a' ]; aft[len] = '\0'; return;
} void getNext( char* s, int* next )
{
int length = len;
int i = , j = -;
next[] = -;
while ( i < length )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
next[i] = j;
}
else j = next[j];
}
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%s", table );
scanf( "%s", ori );
init();
getNext( aft, next ); int ans = len;
//printf("next[%d] = %d\n", ans, next[ans] );
while ( next[ans] > len/ ) ans = next[ans];
ans = len - next[ans];
//printf( "ans = %d\n", ans );
for ( int i = ; i < ans; ++i )
printf( "%c", ori[i] );
for ( int i = ; i < ans; ++i )
printf( "%c", extable[ ori[i] - 'a' ] );
puts("");
}
return ;
}
最新文章
- Android开发-之环境的搭建
- 几个简单的js正则验证
- Oracle 【IT实验室】数据库备份与恢复之一:exp/imp(导出与导入&;装库与卸库)
- ArcGIS Engine开发之旅10--空间参考及坐标转换
- Sublime怎样新建HTML文档
- 转:Oracle中的rownum不能使用大于>;的问题
- Mysql避免全表扫描sql查询优化 .
- apache AH01630: client denied by server configuration错误解决方法
- Windows命令行命令集锦
- 第三节:ThreadPool的线程开启、线程等待、线程池的设置、定时功能
- 将汉字转化为拼音的js插件
- 在a标签内添加hover样式的方法:
- 【转】linux下查看磁盘分区的文件系统格式
- Unity3D学习笔记(二十八):Editor
- ubuntu下常用命令
- Windows网络命令
- cropper图片剪裁 , .toBlob()报错
- hibernate:inverse、cascade,一对多、多对多详解
- 跟着太白老师学python day10 函数嵌套, global , nonlocal
- iOS开发基础控件--UIButton