T2 选ID trie树

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;
}
相关文章
相关标签/搜索