最长不重叠前后缀

题目描述

给定一个字符串，返回最长的既出现在字符串开头又出现在字符串结尾，且不重叠的子串。例如，对于字符串 "abXab"，结果是 "ab"。

输入格式

输入以如下格式从标准输入中给出。

s

输出格式

输出以如下格式输出到标准输出中。

result

样例

abXYab

"ab"

xx

"x"

xxx

"x"

样例解释

对于字符串 abXYab，"ab" 是最长的既出现在开头又出现在结尾且不重叠的子串。 对于字符串 xx，"x" 是最长的既出现在开头又出现在结尾且不重叠的子串。 对于字符串 xxx，"x" 是最长的既出现在开头又出现在结尾且不重叠的子串。

数据范围

字符串 $s$ 的长度在 $1$ 到 $10^5$ 之间。 字符串 $s$ 由小写英文字母组成。