URAL 1684. Jack's Last Word ( KMP next函数应用 )
2024-08-23 00:54:20
题意:问第二行的串能不能恰好分割成几个串,使得这几个串都是第一行串的前缀。如果是,输出No, 并输出这几个串,否则输出Yes。
这题是Special Judge,把两个串连接起来,中间用一个未出现过的字符分隔开。
从新串串尾开始,每次向前移动一个最大前缀的长度。如果期间遇到nextval值为0的点(即没有公共前缀),则肯定不行。
记录分割点位置,输出结果。
#include <cstdio>
#include <cstring>
#include <cstdlib> const int MAXN = ; char str[MAXN << ];
char tmp[MAXN];
int nextval[MAXN << ];
int strL, len;
bool flag[MAXN]; 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];
}
return;
} int main()
{
while ( scanf( "%s", str ) == )
{
strL = strlen(str);
scanf( "%s", tmp );
str[strL] = '$';
strcpy( &str[strL+], tmp );
len = strlen(str);
getNext( str, nextval ); //puts(str); memset( flag, false, sizeof(flag) );
bool ok = false;
for ( int i = len; i > strL+; )
{
int tp = nextval[i];
if ( tp == ) ok = true;
if ( i-(strL+)- >= ) flag[i-(strL+)-] = true;
//printf( "i=%d tp=%d\n", i, tp );
if ( tp > ) i -= tp;
else --i;
} if ( ok ) puts("Yes");
else
{
puts("No");
for ( int i = ; i < len-strL-; ++i )
{
putchar( tmp[i] );
if ( i != len-strL- && flag[i] ) putchar(' ');
}
puts("");
}
}
return ;
}
最新文章
- makefile小例子
- 边表+SPFA
- [Aaronyang] 写给自己的WPF4.5 失传的第一本古老秘籍[多扩展显示器编程]
- HDU 4925 Apple Tree(模拟题)
- cookie 使用笔记
- [你必须知道的.NET]第三十五回,判断dll是debug还是release,这是个问题
- Unity之屏幕画线
- HDU 1269 迷宫城堡 【强联通分量(模版题)】
- 解决Android AVD启动报错问题
- 【递推+矩阵快速幂】【HDU2604】【Queuing】
- uva 11077 置换
- angular.js的ui-router总结
- Spring Cloud Context模块
- JavaScript获取键盘事件
- java中JDBC连接Oracle数据库
- 百度地图自定义icon,定位偏移问题
- 微信Access Token 缓存方法
- WIN10系统如何取消右下角的通知菜单,通知图标
- KEIL C51程序中如何嵌入汇编
- laravel运行慢是怎么回事?