Orange Boy Can You Solve It Out? Ep.9

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

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/181
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录