题目链接：
https://codeforces.com/gym/100935/problem/F
题面：F. A Poet Computer
time limit per test2 seconds
memory limit per test64 megabytes
inputstandard input
outputstandard output
The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constructed a dictionary of words, They are interested only in the longest common suffix, That is, a suffix common to three or more words in the dictionary… A suffix is any substring that starts from some arbitrary position in the string and reaches the end of the string. As the ACM team was also preparing for the ACM-TCPC2015 contest, they figured that the contestants can help in solving this problem. Your task is to write a program that finds a longest common suffix in a dictionary of words. An entry in the dictionary is a word of English letters only. Small letters are the same as capital letters. You can assume that there is exactly one unique solution for every test case.
Input
The first line of the input contains an integer T, the number of test cases. Each test case starts with a line containing one integer K, then K lines follow, each containing one string “Si” that represents an entry in the dictionary. 0 < T ≤ 50 |Si| ≤ 100 0 < K ≤ 1000
Output
For each test case, print on the first line “Case c:” where ‘c’ is the test case number. On the second line you should print an integer denoting the length of the longest common suffix and another integer denoting how many words have the suffix appeared in.
Examples
input
2
4
cocochannel
chrisschannel
MBCchannel
controlpanel
5
superman
batman
ironman
chrissbrown
MyCrown
output
Case 1:
7 3
Case 2:
3 3
思路：这题应该用字典树来做，这里提供另一种思路。
首先是后缀数组，我们很容易想到哈希和二分。题干要求找出其最长的后缀串（出现次数不少于3），所以我们应该从后向前哈希。
然后通过sort排序（升序降序都可以）
最后我们考虑如何找出最长的后缀串且其出现次数不少于3，我们可以先用mlen记录最长的公共后缀串（注意这不一定是答案，因为其出现次数可能只是2）。然后，我们枚举[0，mlen)作为公共后缀串长度，通过比较哈希值来判断后缀串是否相等并记录次数（可以用map实现），如果其出现次数超过2，那么更新maxn和ans,即最长长度和出现次数，最后注意map在每次使用完之后的清0；
（Ps，这道题告诉我们要审题认真，题面中的
That is, a suffix common to three or more words in the dictionary
Small letters are the same as capital letters.
最开始被忽略了，搞得我连样例都没有弄懂；
然后就是实现方法，避免先入为主的思考，比如按顺序排列后如果字符串和它上一个字符串与它的上一个和上上个公共后缀长度不一样，那么计数归零；这样其实是错误了，太武断了；可能有这样一组数据
6
ab
ab
ab
ab
ab
a
）
具体参考代码实现
AC代码
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstring>
#include <string.h>
#include <cmath>
#include <cstdlib>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define Pi acos(-1.0)
#define Inf 0x3f3f3f3f
#define Mid ll + ((rr - ll) >> 1)
#define Lson id << 1, ll, Mid
#define Rson id << 1 | 1, Mid + 1, rr
#define Fir first
#define Sec second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int K = 1e3 + 5, N = 1e2 + 5, P = 131;
ULL p[N];
int maxn, cnt, ans, mlen;
struct node{
char s[N];
ULL h[N];
int len;
}a[K];
int t;
map <ULL, int> mp;
int calcu(int r1, int r2, const ULL *h1, const ULL *h2){
int ll = 0, rr = min(r1, r2) - 1;
while(ll < rr){
int mid = (ll + rr + 1) >> 1;
ULL t1, t2;
t1 = h1[mid];
t2 = h2[mid];
if(t1 == t2) ll = mid;
else rr = mid - 1;
}
return ll ? ll + 1 : (h1[0] == h2[0] ? 1 : 0);
}
int main(){
scanf("%d", &t);
p[0] = 1;
for(int i = 1; i < N; ++i) p[i] = p[i - 1] * P;
for(int k = 1; k <= t; ++k){
int m;
scanf("%d", &m); //m : k
maxn = -Inf; cnt = 0; ans = 0; mlen = 0;
for(int i = 1; i <= m; ++i){
char tmp[N];
scanf("%s", tmp);
a[i].len = strlen(tmp);
for(int j = 0; j < a[i].len; ++j){
a[i].s[j] = tmp[a[i].len - 1 - j];
if(a[i].s[j] >= 'A' && a[i].s[j] <= 'Z') a[i].s[j] += 32;
a[i].h[j] = a[i].h[j - 1] * P + a[i].s[j] - 96;
}
a[i].s[a[i].len] = '\0';
//printf("%s\n", a[i].s);
}
sort(a + 1, a + m + 1, [](const node &x, const node &y){
int l = calcu(x.len, y.len, x.h, y.h);
if(l > mlen) mlen = l;
return x.s[l] < y.s[l];
});
//for(int i = 1; i <= m; ++i) printf("1 :%s\n", a[i].s);
for(int i = 0; i < mlen; ++i){
for(int j = 1; j <= m; ++j)
if(a[j].len - 1 >= i){
++mp[a[j].h[i]];
if(mp[a[j].h[i]] > 2)
maxn = i + 1, ans = mp[a[j].h[i]];
}
mp.clear();
}
printf("Case %d:\n%d %d\n", k, maxn, ans);
}
system("pause");
return 0;
}