简单 Trie 树的应用
val 数组是用来表示经过该点的字符串的个数, same 表示在该点结束的字符串的个数. 主要分三个部分, 一个是比当前字符串短的, 和当前字符串相同的 (注意该种情况下比较的次数位 2*(n+1),n 是字符串长度, 因为最后还要比较'\0'), 比当前字符串长的.
- #include<bits/stdc++.h>
- #define _for(i,a,b) for(int i=a;i<=b;i++)
- using namespace std;
- typedef long long ll;
- const int mod =1e6+7;
- double esp=1e-6;
- int INF =0x3f3f3f3f;
- const int inf = 1<<28;
- const int MAXN=5e6+10;
- int ch[MAXN][70];
- int val[MAXN];
- int same[MAXN];
- struct Trie
- {
- ll ans;
- int sz;
- Trie()
- {
- sz=1;
- memset(ch,0,sizeof(ch));
- memset(val,0,sizeof(val));
- memset(same,0,sizeof(same));
- ans=0;
- }
- int idx(char x)
- {
- if(x>='0'&&x<='9')return x-'0';
- else if(x>='A'&&x<='Z')return x-'A'+10;
- else if(x>='a'&&x<='z')return x-'a'+36;
- }
- void INSERT(char *s)
- {
- int u=0,n=strlen(s);
- for(int i=0;i<n;i++)
- {
- int v=idx(s[i]);
- if(ch[u][v]==0)
- {
- ans+=val[u]*(2*i+1);
- ch[u][v]=sz++;
- }
- else
- {
- ans+=(val[u]-val[ch[u][v]])*(2*i+1);
- }
- val[u]++;
- u=ch[u][v];
- }// 比当前串短的
- ans+=(same[u]*2*(n+1));// 和当前串相同的
- ans+=(val[u]-same[u])*(2*n+1);// 比当前串长的
- val[u]++;
- same[u]++;
- }
- };
- char s[2000];
- int main()
- {
- int Case=0,t;
- while(~scanf("%d",&t))
- {
- if(t==0)break;
- Trie tmp;
- for(int i=0;i<t;i++)
- {
- scanf("%s",s);
- tmp.INSERT(s);
- }
- printf("Case %d: %lld\n",++Case,tmp.ans);
- }
- }
来源: http://www.bubuko.com/infodetail-3414190.html