思路:
将每个字符串的原文的所有后缀和反转后的所有后缀都插入到Trie中。
同时Trie中的节点维护一个值 --- 该节点下面包含了多少个不同单词的节点。
然后统计这个值等于N的最深的节点,其深度就是答案了。
后缀Trie并不是好的解法。有人说用后缀数组也能做的,但是想不出来。
#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;
}