---
title: "前缀统计"
created: 2025-11-28
tags:
  - 算法
---

# 前缀统计

## 题目 [前缀统计](https://www.acwing.com/problem/content/description/144/)

![[image-6f5a1029.png]]

## 思路分析

看一堆字符串里有多少个是串S的前缀

实际是就是在查询S的时候 累加一下路上遇到了多少个字符串

（在每个结点有个cnt记录该处有多少个以该单词结尾的串）

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int son[N][26],idx;

int cnt[N];

char str[N];

int n,m;

void insert(char *str){

    int p=0;

    for(int i=0;str[i];i++){

        int u=str[i]-'a';

        if(!son[p][u])

            son[p][u]=++idx;

        p=son[p][u];

    }

    cnt[p]++;

}

int query(char *str){

    int p=0,res=0;

    for(int i=0;str[i];i++){

        int u=str[i]-'a';

        if(!son[p][u])

            return res;

        p=son[p][u];

        res+=cnt[p];

    }

    return res;

}

int main()

{

    cin>>n>>m;

    while(n--){

        cin>>str;

        insert(str);

    }

    while(m--){

        cin>>str;

        cout<<query(str)<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/串相关模型/字典树/trie树/trie树|trie树]] 🏠 [[00-刷题理模型]] ➡️ [[加密信息|加密信息]]