思考题 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