文章

9

粉丝

40

获赞

25

访问

1.8k

头像
前缀字符串 题解:
P1098 中山大学2018年机试
发布于2025年1月16日 12:23
阅读数 213

求助为何这样通过率为0,根据所有的字符串构造一棵Trie树,利用深度优先遍历寻找Trie树叶子节点的个数。由于示例“kdfa”是“kdfa”的前缀,故统计到叶子节点时,只有cnt[p]==1时才将该字符串统计进去,避免了相同字符串的统计。测试用例在本地ide中能够正确表示,求指教,本代码还有什么问题?

//Trie树
#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx = 1;
int leafnum;

void insert(string str){
    int p = 0;
    for(int i = 0;str[i];i ++){
        int c = str[i] - 'a';
        if(!son[p][c]) son[p][c] = idx++;
        p = son[p][c];
    }
    cnt[p]++;
}

void countleaf(int p){
    bool flag = false;
    for(int i = 0;i < 26;i ++){
        if(son[p][i]) {
            flag = true;
            countleaf(son[p][i]);
        }
    }
    if(!flag && cnt[p] == 1) leafnum ++;
}

int main(){
   int n;
   while(cin>>n){
        if(n == 0) break;
        leafnum = 0;
        memset(son,0,sizeof(son));
        memset(cnt,0,sizeof(cnt));
        idx = 1;
        string str;
        while(n--){
        ...
登录查看完整内容


登录后发布评论

2 条评论
快乐小土狗
2025年1月16日 14:20

题目好像没说是小写字母,也没说一定是字母,说的是字符

赞(0)

zcq107 : 回复 快乐小土狗: 破案了!谢谢快乐小狗!

2025年1月16日 16:15