【bzoj1174】[Balkan2007]Toponyms

2014年4月2日2,3744

Description

给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.

Input

第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 总输入不超过20000字符

Output

 a single line with an integer representing the maximal level of complexity Lc(T).

Sample Input

7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi

Sample Output

24

题解

首先写了个re不断的字典树

 

  • ___2015年5月21日 上午12:34 回复

    黄学长,这似乎并不是正解,普通字典树节点超过400w个,过不了,能贴个正解不。

    #1  
    • 黄维2016年6月26日 下午10:29 回复

      改写成链表方式就可以了

      #11
  • 黄维2015年12月4日 下午8:16 回复

    +1

    #2  
  • 钟子谦2016年7月24日 下午5:59 回复

    gg

    #3