← 返回题目列表

Codeforces · 2010/C2

C2. 消息传输错误(硬版)

中文机器翻译题面 查看原题

这是问题的一个更困难的版本。它与简单方法的区别仅在于有限制。

在 Berland 州立大学,服务器之间的本地网络并不总是运行无错误。当连续发送两条相同的消息时,可能会发生错误,导致两条消息合并为一条。在此合并中,第一条消息的结尾与第二条消息的开头重合。当然,合并只能发生在相同的字符处。合并的长度必须是小于消息文本长度的正数。

例如,当连续传输两条消息“abrakadabra”时,传输时可能会出现所描述类型的错误,从而产生类似“abrakadabrakadabra”或“abrakadabrakadabra”的消息(在第一种情况下,合并发生在一个字符处,在第二种情况下,合并发生在四个字符处)。

给定接收到的消息t,确定这是否可能是本地网络操作中所描述类型的错误的结果,如果是,则确定s的可能值。

两条消息完全重叠的情况不应被视为错误。例如,如果接收到的消息是“abcd”,则应该认为其中没有错误。同样,简单地将一条消息附加到另一条消息并不表示出现错误。例如,如果接收到的消息是“abcabc”,也应该认为其中没有错误。

输入

输入由单个非空字符串 t 组成,该字符串由拉丁字母的小写字母组成。字符串t的长度不超过4·105个字符。

输出

如果消息 t 不能包含错误,则在单行输出中输出“NO”(不带引号)。

否则,在第一行中输出“YES”(不带引号),并在下一行中输出字符串 s — 可能导致错误的消息。如果有多个可能的答案,则任何一个都可以接受。

示例

输入 #1

abrakadabrabrakadabra

输出 #1

YES
abrakadabra

输入 #2

acacacaca

输出 #2

YES
acacaca

输入 #3

abcabc

输出 #3

NO

输入#4

abababab

输出#4

YES
ababab

输入 #5

tatbt

输出 #5

NO

注意

在第二个示例中,合适的答案也可以是字符串“acacaca”。