TB椰程 TypeBuddy 打字搭子

字典树 Trie

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 502 字

沿字符向下建链，前缀结构与词频统计

  • 字符串
  • 字典树

前置内容

正文

// 字典树 Trie：前缀结构
// 每个节点存子节点指针
// 沿字符向下走插入 / 查询
// 适合异或最大 / 词频统计
#include <cstdio>
int ch[100005][26], cnt = 0;
int ed[100005], tot = 0;
// 插入一个单词
void insert(char* s) {
    int u = 0;
    // 逐字符向下建链
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        // 无子节点则新建
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    // 单词结尾计数 +1
    ed[u]++;
}
int main() {
    char w[25];
    scanf("%s", w);
    // 插入后查词尾计数
    insert(w);
    printf("%d", ed[0]);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK