首页 > 代码库 > UVALive 5913 字典树

UVALive 5913 字典树

2024-07-12 22:40:54   222人阅读

先输入n个字符串的字典，每个字符串的前缀+后缀可以组成新的合法字符串，但肯定是有重复的，问从给定的字符串，生成的所有可能的字符串为多少个

把前缀和后缀压入字典树，达到前缀和后缀的去重，首先的总和即为前缀数目乘以后缀数目，之后为了去重，记录每个前后缀非第一个相同的每个字母，则每个相同字母必定会产生重复。减掉即可。。还要注意，len=1的字符串特判。。注意细节处理

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing namespace std;int n;LL sum1,sum2;LL num1[26],num2[26];struct node{    int ch[400000][26];    int cnt;    void init()    {        memset(ch,0,sizeof ch);        cnt=1;    }    void inserts(char* str)    {        int rt=0;        int k=0;        while (str[k])        {            int q=str[k]-‘a‘;            if (ch[rt][q]==0){                ch[rt][q]=cnt++;                sum1++;                if (k>0) num1[q]++;            }            rt=ch[rt][q];            k++;        }    }    void inserts2(char* str)    {        int rt=0;        int k=0;        while (str[k])        {            int q=str[k]-‘a‘;            if (ch[rt][q]==0){                ch[rt][q]=cnt++;                sum2++;                if (k>0) num2[q]++;            }            rt=ch[rt][q];            k++;        }    }}T1,T2;char s[50];int len;int one[26];int main(){    while (scanf("%d",&n)!=EOF)    {        T1.init();        T2.init();        sum1=sum2=0;        memset(one,0,sizeof one);        memset(num1,0,sizeof num1);        memset(num2,0,sizeof num2);        for (int i=0;i<n;i++){            scanf("%s",s);            T1.inserts(s);            len=strlen(s);            if (len==1) {one[s[0]-‘a‘]=1;}            reverse(s,s+len);            T2.inserts2(s);        }        LL ans=sum1*sum2;        //cout<<sum1<<" "<<sum2<<endl;        for (int i=0;i<26;i++){            if (one[i]) ans++;            ans-=num1[i]*num2[i];        }        printf("%lld\n",ans);    }    return 0;}

　　


联系
我们