T2 选ID
Description
机房似乎有许多人没有 ID，热心同志小 A 为了服务人民，所有决定帮大家找一个合适的 ID。
小 A 觉得一个合适的 ID，和这个人的相关程度应该是比较高的，就像他的 ID 里有他的名字缩写一样。为了量化这个相关程度，他定义一个人的名字 (S) 和他的 ID (T) 的匹配值的大小为(lcp)((S),(T))。现在有 (n) 个人，小 A 想好了 (n) 个 ID，他想知道如果把 ID 分配给机房众人，最后能够得到的最大的匹配值之和是多少。
Input Format
第一行一个 (n)，表示人数。
接下来 (n) 行，每行一个字符串，表示一个人的姓名。
接下来 (n) 行，每行一个字符串，表示一个 ID。
保证姓名和 ID 只包含小写字母。
Output
输出一行表示最大的匹配值。
Solution
我们可以直接 利用(trie)树来贪心，树上每一个点都可以对答案产生(x)的贡献（(x)为多少个这样的节点），而是否产生取决于(T)字符串是否可以到达这个节点，所以贪心来做，每搜到一个节点就判断(x)是否大于0，即还能不能产生贡献，若能则(ans++),再把当前节点的x--，不能就继续搜下去。注意，一旦在树上失配就return，以保证前面产生贡献的点全满足前缀。
#include<bits/stdc++.h>
#define N 1000010
#define M 30000010
using namespace std;
int tr[N][26],val[N];
int n,now,cnt,ans;
char s[M];
void ins()
{
int now=0,len=strlen(s);
for(int i=0;i<len;i++)
{
if(!tr[now][s[i]-'a']) tr[now][s[i]-'a']=++cnt;
now=tr[now][s[i]-'a'];
val[now]++;
}
}
void sol()
{
int now=0,len=strlen(s);
for(int i=0;i<len;i++)
{
if(!tr[now][s[i]-'a']) return;
now=tr[now][s[i]-'a'];
if(val[now])
{
ans++,val[now]--;
}
}
}
int main()
{
int i,j;
//scanf("%d",&n);
cin>>n;
for(i=1;i<=n;i++) scanf("%s",s),ins();
for(i=1;i<=n;i++) scanf("%s",s),sol();
printf("%d",ans);
return 0;
}