どこでも探そう!
非常に長いテキストt
が与えられているとして、この会社では、次の条件をすべて満たす最長の部分文字列s
を探したいと考えています:
s
がt
の接頭辞(prefix)になっているs
がt
の接尾辞(suffix)になっているs
がt
の部分文字列(substring)になっている
あなたなら、これをどのように見つけますか?
入力
入力としては、1 行だけにテキストt
が与えられます (1 ≤ |t| ≤ )。
出力
条件をすべて満たす部分文字列s
のうち最長の文字列を出力してください。もしそのような部分文字列が存在しない場合は、Impossible
を出力してください。
例
Input | Output |
---|---|
fixfixfix | fix |
hello | Impossible |
abcabdab | ab |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB