51nod-1526-贪心+Trie

题目来源： CodeForces

基准时间限制：1 秒空间限制：131072 KB 分值: 320 难度：7级算法题

关注

班里有n个同学。老师为他们选了n个笔名。现在要把这些笔名分配给每一个同学，每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为a，真名为b，则他们之间的相关度为lcp(a,b)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。

现在要求分配笔名，使得匹配质量最大。

样例解释：

· bill → bilbo (lcp = 3)

· galya → galadriel (lcp = 3)

· gennady → gendalf (lcp = 3)

· toshik → torin (lcp = 2)

· boris → smaug (lcp = 0)

Input

单组测试数据。

第一行有一个整数n (1≤n≤100000)，表示班级中同学的数目。

接下来n行，表示每一个同学的真名，每一个名字是非空串，且由小写字母组成。

名字可能重复。

最后n行是老师已经安排好的笔名。每一个笔名是一个非空串，且由小写字母组成。

笔名可能重复。

输入的字符总数目不超过 800000。

Output

输出最大的匹配质量。

Input示例

样例输入1

5

gennady

galya

boris

bill

toshik

bilbo

torin

gendalf

smaug

galadriel

Output示例

样例输出1

11
 很容易想到一个贪心的算法是，对于每一个笔名，把他用在使得他贡献最大的人身上，字符串前缀最大，数据量又很大，考虑使用字典树把人名存下，用笔名在树上匹配。思路是对的但出了一个bug。
如果在某个称号还未配对时，他的最优人被其他人用了咋整。可以这样想，每个结点统计前缀个数vis[u],匹配时只要vis[u]存在就让ans++;累计一个贡献，最后就是正解。假如这个前缀有多个，那就是
按贡献大小给占用他的人，如果个数有限的话，那么势必会有一些名称的匹配贡献是0，我们当然要让匹配的少的那些为零。这个过程在代码里不会呈现但不会影响最终结果。
  假如有笔名: abxx abccc   有人名: abccx 有且仅有一个
当abxx先找时，相当于贡献了'a','b'两个贡献，余下的不再匹配树上这两个字符对应节点的价值也会减一（归零），当abccc进行匹配时，会做出'c','c'两个贡献
这样一共进行了四个贡献，虽然看起来abccc前缀并没有完全匹配，但只不过是"abxx"提前替他匹配了一小段前缀而已。

 #include<bits/stdc++.h>

 using  namespace std;

 int ch[][];

 int sz=,ans=;

 int vis[];

 char s[];

 void insert(char *s){

     int u=,n=strlen(s);

     for(int i=;i<n;++i){

         int c=s[i]-'a';

         if(!ch[u][c]) ch[u][c]=sz++;

         vis[u]++;

         u=ch[u][c];

     }

     vis[u]++;

 }

 void match(char *s){

     int i,u=,n=strlen(s),r=,ret=;

     for(i=;i<n;++i){

         int c=s[i]-'a';

         if(ch[u][c]==) return ;

         u=ch[u][c];

         if(vis[u]){

         vis[u]--;

         ans++;

         }

     }

 }

 int main()

 {

     int n,m,i,j,k;

     cin>>n;

         for(i=;i<=n;++i){

             scanf("%s",s);

             insert(s);

         }

         for(i=;i<=n;++i){

             scanf("%s",s);

             match(s);

         }

         printf("%d\n",ans);

     return ;

 }

 /*

 5

 gennady

 galya

 boris

 bill

 toshik

 bilbo

 torin

 gendalf

 smaug

 galadriel

 */

LCP

51nod-1526-贪心+Trie