CF1063F String Journey

We call a sequence of strings $ t_{1},...,t_{k} $ a journey of length $ k $ , if for each $ i>1 $ $ t_{i} $ is a substring of $ t_{i-1} $ and length of $ t_{i} $ is strictly less than length of $ t_{i-1} $ . For example, $ {ab,b} $ is a journey, but $ {ab,c} $ and $ {a,a} $ are not. Define a journey on string $ s $ as journey $ t_{1},...,t_{k} $ , such that all its parts can be nested inside $ s $ in such a way that there exists a sequence of strings $ u_{1},...,u_{k+1} $ (each of these strings can be empty) and $ s=u_{1}t_{1}u_{2}t_{2}...\ u_{k}t_{k}u_{k+1} $ . As an example, $ {ab,b} $ is a journey on string $ abb $ , but not on $ bab $ because the journey strings $ t_{i} $ should appear from the left to the right. The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string $ s $ .

N/A

N/A

In the first sample, the string journey of maximum length is $ {abcd,bc,c} $ . In the second sample, one of the suitable journeys is $ {bb,b} $ .