原根

最优解

考虑建立一棵字典树,一个字符串为另一个字符串的前缀,当且仅当它对应的节点是另一个节点的祖先。所以我们建立完字典树之后,标记一下每个结点作为字符串的终点几次。最后从根开始往下搜索,当搜索到一个结束位置的时候,如果这个结束位置只代表一个字符串那么就统计入答案,不然就不统计。并且搜到一个结束位置就不用往下搜了,因为下面即使搜到了结束位置也不可能是原根,当前的结束位置必然会是它的祖先。
时间复杂度和空间复杂度都是

int ch[1000005][26];
int is_over[1000005];
int dfs(int u){
    if(is_over[u]){
        return (is_over[u] == 1);
    }
    int ans = 0;
    for(int i = 0; i < 26; ++i) if(ch[u][i]) ans += dfs(ch[u][i]);
    return ans;
}
int solve(int n, vector<string> s){
    int tot = 0; int rt = ++tot;
    memset(ch[rt], 0, sizeof ch[rt]); is_over[rt] = 0;
    for(int i = 0; i < n; ++i){
        int p = rt;
        for(int j = 0; j < s[i].size(); ++j){
            int x = s[i][j] - 'a';
            if(!ch[p][x]) {
                ch[p][x] = ++tot; memset(ch[tot], 0, sizeof ch[tot]);  is_over[tot] = 0;
            }
            p = ch[p][x]; 
        }
        is_over[p]++;
    }
    return dfs(rt);
}
全部评论

相关推荐

Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务