[字符串][Trie][x] UVALive 5913 Dictionary Size

前后缀处理与去重

题目链接

题意：给出n个字符串，要求求出所有的前后缀组成的字符串种类数。

思路：比较简单的一题。 用Trie存储所有的字符串，可以算出所有不同的前缀数，然后把字符串全部反向再插入到另一个Trie，得出所有的后缀数量。二者相乘可以得到所有的可能结果，但是会有重复，所以要去重。去重也很简单，画一画样例可以看出来一定是算出来两个Trie里面的相同的字符出现的次数，每一个字符结点出现一次就会有一个重复，这样减去所有的重复即可。但是直接这样算会有错误，因为可能会产生有的前缀为空后缀为一个不完整字符串，这样是不满足题目要求的，所以在统计结点数量的时候只统计长度大于1的结点（在Trie里深度大于1），然后这样构造出来的全部是满足要求的字符串而且没有重复，但是仍然有一个bug是有的字符串只有一个字符，而上述方法是只能构造出来最小长度为2的字符串的，因此要另外处理这些长度为1的字符最后加到答案里。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e4 + 5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;

char str[45];

struct Trie{
    int ch[maxn*50][26],cnt[30];
    int root,sz;
    void init(){
        root=sz=0;
        memset(ch[0],-1,sizeof(ch[0]));
        memset(cnt,0,sizeof(cnt));
    }
    void insert(char* s){
        int len=strlen(s),c,u=0,nxt;
        for(int i=0;i<len;i++){
            c=s[i]-'a';
            if(ch[u][c]==-1){
                memset(ch[++sz],-1,sizeof(ch[0]));
                ch[u][c]=sz;
            }
            u=ch[u][c];
        }
    }

    int dfs(int x){
        for(int i=0;i<26;i++){
            if(ch[x][i]!=-1){
                cnt[i]+=(x!=0);
                dfs(ch[x][i]);
            }
        }
    }
}tr,rtr;


int cc[30];

int main()
{
    int n;
    while(~scanf("%d\n",&n)){
        tr.init();
        rtr.init();
        memset(cc,0,sizeof(cc));
        for(int i=1;i<=n;i++){
            scanf(" %s",str);
            tr.insert(str);
            int len=strlen(str);
            if(len==1)
                cc[str[0]-'a']=1;
            for(int i=0;i<=((len-1)/2);i++){
                swap(str[i],str[len-1-i]);
            }
            rtr.insert(str);
        }
        LL a=tr.sz,b=rtr.sz,ans=0;
        tr.dfs(tr.root);
        rtr.dfs(rtr.root);
        ans=a*b;
        for(int i=0;i<26;i++){
            ans+=cc[i];
            ans-=1LL*tr.cnt[i]*rtr.cnt[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
in:
3
abc
def
abef

out:
30

in:
5
acgf
acgfwk
abccf
abcde
dcfef

out:
350
*/