Solved!
Difficulty: Div2B-Div2C

思考题 that seems easy

A perfect word

Given N strings. Find out a longest string so that each substring of it is one of the N strings.

Example

Input
str={a,t,at,orange}
Output
at

Constriants

Subtask 1(30%):N<=100
Subtask 2(30%):N<=1000
Subtask 3(40%):N<=100000

Orange boy solved the problem after 1 min

Solution By XGN

Sort the strings by increasing length. A string is OK to be the answer if its length is 1 or all the substring of its length-1 is OK. Then at last find out the answer.
For example:
a -OK
t -OK
at -'a' is OK and 't' is OK, so OK
ta -OK
ata -'at' is OK and 'ta' is OK, so OK
atat ->'ata' is OK but 'tat' is not, so no ok