听说你会KMP
题号：NC214198
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

KMP算法堪称匹配算法中的经典，相比较与暴力匹配，改进了时间复杂度，但是你真的学会了KMP吗?
小明同学在学KMP算法的时候发现其中的next数组特别有意思，表示字符串前后缀相同的个数，这样就可以高效率回溯。
现在小明同学遇到一个问题，你能不能帮他找出在字符串中，在开始出现、在结尾出现且在中间部分(不含首位和末位)出现的最长子串。

输入描述:

字符串的长度在1到106（含）之间，由小写字母组成。

输出描述:

最长子串，如果不存在合适的子串，打印不带引号的“Hello KMP!”。
示例1

输入

复制 
asdfghasderrtasd

输出

复制 
asd