本文共 2500 字，大约阅读时间需要 8 分钟。

单词表

时间限制: 1 Sec 内存限制: 128 MB

题目描述

hzwer获得了一个n个单词的单词表，其中每个字符都是小写字母，现在，他想和他的妹子研究一下这个单词表。 设编号为u的单词与编号为v的单词（u <v ）构成单词对(u ,v)，记两个单词最长公共前缀为S1(u ,v)，最长公共后缀为S2(u ,v)。 hzwer从S1入手，他想知道，所有单词对生成的S1串中，长度最大的串，如果有多个，那么他在其中选择字典序最小的，并且你要告诉他S1串为该串的单词对数，而他的妹子则关心S2，要求类似。 但是hzwer要和他的妹子去度假，所以这个问题就交给你了。 保证至少存在一个长度大于0的S1串和S2串。 输入 第一行一个正整数n，表示单词个数。 接下来n行，每行一个字符串，表示一个单词。 输出 第一行输出最长的基础上字典序最小的S1串，以及S1串为该串的单词对个数，用一个空格隔开。 第二行输出最长的基础上字典序最小的S2串，以及S2串为该串的单词对个数，用一个空格隔开。 样例输入 Copy 5 bbbaa aacbb bbdaa aaaaa bbcaa 样例输出 Copy aa 1 aa 6 提示 对于100%的数据，2 ≤ n ≤ 50000，字符串总长不超过500000，保证单词表中所有字符都是小写字母，答案中S1串和S2串非空。

最近复习了下字典树，让后在巨巨的指导下补了这个题。

字典树在统计前缀后缀都比较好用。在构建字典树的时候，每一个点 idx 对应的 cnt [ idx ] 的数量即为以这个字母为结尾的公共前缀个数。对于这个题来说，当 cnt [ idx ] > 1 的时候即符合题目中要求的条件。 直接考虑dfs爆搜一遍，每次枚举 a ~ z 字母，如果存在儿子并且 cnt [ idx ] > 1 那么就可以扩展这个前缀，使前缀变得更长。 对于后缀是一样处理，无非是把字符串反过来，反向建一颗字典树，正是由于反向建树，所以原来要求的字典序最小，在求这个后缀的时候应该是字典序最大的。这个一开始没想明白，dfs的时候从小到大枚举字母，以为贪心找字典序最小就不需要判断长度相等的时候了，一直wa。所以 (1)长度变大的时候，理所当然的应该更新答案。 (2)长度与原来相等的时候，需要检查一下是否可以更新。 最后还要求输出单词的对数，直接套公式：n * ( n - 1 ) / 2 。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105903934 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！