思路：
將每個(gè)字符串的原文的所有后綴和反轉(zhuǎn)后的所有后綴都插入到Trie中。
同時(shí)Trie中的節(jié)點(diǎn)維護(hù)一個(gè)值 --- 該節(jié)點(diǎn)下面包含了多少個(gè)不同單詞的節(jié)點(diǎn)。
然后統(tǒng)計(jì)這個(gè)值等于N的最深的節(jié)點(diǎn)，其深度就是答案了。
后綴Trie并不是好的解法。有人說用后綴數(shù)組也能做的，但是想不出來。
#include <stdio.h>
#include <string.h>
struct node 
{
char ch;
int ts, cnt;
struct node *sib, *child;
};
struct node nodes[65536], root;
int nodes_cnt;
int N, T;
int ts, ans;
inline struct node *insert(struct node *q, char ch, int depth)
{
struct node *t;
for (t = q->child; t; t = t->sib)
if (t->ch == ch)
break;
if (!t) {
t = &nodes[nodes_cnt++];
t->ch = ch;
t->cnt = 0;
t->child = NULL;
t->sib = q->child;
q->child = t;
}
if (t->ts != ts) {
t->ts = ts;
t->cnt++;
}
if (t->cnt == N && depth > ans)
ans = depth;
return t;
}
int main()
{
int i, j, k, len;
char str[128];
struct node *t;
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
ans = 0;
nodes_cnt = 0;
root.child = root.sib = NULL;
root.cnt = 0;
for (i = 0; i < N; i++) {
scanf("%s", str);
ts++;
len = strlen(str);
for (j = 0; j < len; j++) {
t = &root;
for (k = j; k < len; k++)
t = insert(t, str[k], k - j + 1);
}
for (j = len - 1; j >= 0; j--) {
t = &root;
for (k = j; k >= 0; k--)
t = insert(t, str[k], j - k + 1);
}
}
printf("%d\n", ans);
}
return 0;
}