博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
URAL 1684. Jack's Last Word ( KMP next函数应用 )
阅读量:4572 次
发布时间:2019-06-08

本文共 1104 字,大约阅读时间需要 3 分钟。

题意:问第二行的串能不能恰好分割成几个串,使得这几个串都是第一行串的前缀。如果是,输出No, 并输出这几个串,否则输出Yes。

这题是Special Judge,把两个串连接起来,中间用一个未出现过的字符分隔开。

从新串串尾开始,每次向前移动一个最大前缀的长度。如果期间遇到nextval值为0的点(即没有公共前缀),则肯定不行。

记录分割点位置,输出结果。

#include 
#include
#include
const int MAXN = 75010;char str[MAXN << 1];char tmp[MAXN];int nextval[MAXN << 1];int strL, len;bool flag[MAXN];void getNext(char s[],int next[]){ int length=len; int i=0,j=-1; next[0]=-1; while(i
strL+1; ) { int tp = nextval[i]; if ( tp == 0 ) ok = true; if ( i-(strL+1)-1 >= 0 ) flag[i-(strL+1)-1] = true; //printf( "i=%d tp=%d\n", i, tp ); if ( tp > 0 ) i -= tp; else --i; } if ( ok ) puts("Yes"); else { puts("No"); for ( int i = 0; i < len-strL-1; ++i ) { putchar( tmp[i] ); if ( i != len-strL-1 && flag[i] ) putchar(' '); } puts(""); } } return 0;}

 

转载于:https://www.cnblogs.com/GBRgbr/p/3348894.html

你可能感兴趣的文章
底层原理
查看>>
21. Merge Two Sorted Lists
查看>>
创建数组
查看>>
dict使用
查看>>
ASP.NET MVC的帮助类HtmlHelper和UrlHelper
查看>>
02_ListActive中响应事件 并LogCat输出
查看>>
doubleclick adx note
查看>>
Celery框架
查看>>
[c#]asp.net开发微信公众平台(4)关注事件、用户记录、回复文本消息
查看>>
[转载,感觉写的非常详细]DUBBO配置方式详解
查看>>
Android在Eclipse上的环境配置
查看>>
面向对象(五)
查看>>
android平台下使用点九PNG技术
查看>>
Python学习3,列表
查看>>
最长回文子串
查看>>
JAVA基础-JDBC(一)
查看>>
js中for和while运行速度比较
查看>>
算法第5章作业
查看>>
7.9 练习
查看>>
基于ArcGIS JS API的在线专题地图实现
查看>>