51nod1526 分配笔名

传送门: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1526

Solution

很裸的Trie树.先按真名建一棵Trie树,记下每个节点的数量.读入笔名时在Trie树里往下找,如果该节点数量大于0,则答案加1,数量减1;否则跳出循环.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=800005;
char s[N];
int c[N][26],v[N];
int ans,len,n,cnt;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%s",s+1);
        len=strlen(s+1);
        for (int j=1,now=0;j<=len;j++){
            if (!c[now][s[j]-'a'])
                c[now][s[j]-'a']=++cnt;
            now=c[now][s[j]-'a'];
            v[now]++;
        }
    }
    for (int i=1;i<=n;i++){
        scanf("%s",s+1);
        len=strlen(s+1);
        for (int j=1,now=0;j<=len;j++){
            if (!c[now][s[j]-'a']) break;
            now=c[now][s[j]-'a'];
            if (v[now]) ans++,v[now]--;
        }
    }
    printf("%d",ans);
}