题目链接：uva 1519 - Dictionary Size

题目大意：给出n个字符串组成的字典，现在要添加新的单词，从已有单词中选出非空前缀和非空后缀，组成新单词。问说能组成多少个单词。

解题思路：建立一棵前缀树和一棵后缀树，有多少节点即为有多少个前缀，扣除中间的部分即可加上长度为1的字符串即可。

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 400005; const int sigma_size = 26; typedef long long ll; struct Tire { int sz, g[maxn][sigma_size]; int c[sigma_size]; void init (); int idx(char ch); void insert(char* s); }pre, suf; int main () { int N; while (scanf("%d", &N) == 1 && N) { char word[45]; int vis[sigma_size]; memset(vis, 0, sizeof(vis)); pre.init(); suf.init(); for (int i = 0; i < N; i++) { scanf("%s", word); int n = strlen(word); if (n == 1) vis[word[0] - 'a'] = 1; pre.insert(word); reverse(word, word + n); suf.insert(word); } ll ans = (ll)(pre.sz - 1) * (suf.sz - 1); for (int i = 0; i < sigma_size; i++) ans -= (ll)pre.c[i] * suf.c[i] - vis[i]; printf("%lld\n", ans); } return 0; } void Tire::init () { sz = 1; memset(g[0], 0, sizeof(g[0])); memset(c, 0, sizeof(c)); } int Tire::idx (char ch) { return ch - 'a'; } void Tire::insert(char* s) { int u = 0, n = strlen(s); for (int i = 0; i < n; i++) { int v = idx(s[i]); if (g[u][v] == 0) { memset(g[sz], 0, sizeof(g[sz])); g[u][v] = sz++; if (i) c[v]++; } u = g[u][v]; } }