---
title: "加密信息"
created: 2025-11-28
tags:
  - 算法
---

# 加密信息

## 题目 [加密信息](https://www.acwing.com/problem/content/description/4194/)

![[image-6e35fc70.png]]

## 思路分析

M串和N串长度并没有严格大小之分，所以存在两种情况，一种是N串是M串的子串，另一种是M串是N串的子串

对于这两种子串，我们都需要经过Trie树某一个点之后的字符串数量，以及以这个点为结尾的字符串数量

注意 它这的读入是带空格的 110这个字符串 成1 1 0读入 所以用char读入 拼成string

## 代码实现

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

using namespace std;

const int M=500010;

int son[M][2],idx;

int ed[M],st[M];

void insert(string s)

{

    int p=0;

    int len=s.length();

    for(int i=0;i<len;i++){

        int x=s[i]-'0';

        if(!son[p][x])

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

        p=son[p][x];

        st[p]++; //记录经过p结点的字符串数量

        //因为这里可能会重复经过某一个结点就例如样例中的 第二条解密信息，经过了3个相同的1，这里就是为了记录那种情况

    }

    ed[p]++;//这里就是记录以p为叶子结点的字符串的数量

}

int query(string s)

{

    int cnt=0;

    int p=0;

    int len=s.length();

    for(int i=0;i<len;i++){

        int x=s[i]-'0';

        //如果这个点接下来不再匹配，返回的就是以这个点为尾结点的字符串数量

        if(!son[p][x])

            return cnt;//处理的是M串比N串长度大的情况

        p=son[p][x];

        cnt+=ed[p];

    }

    return cnt+st[p]-ed[p];//这里就是处理M串比N串中字符串长度小的情况

    //st[p]-ed[p]就是p结点之后的字符串的个数

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        int k;

        string s;

        cin>>k;

        for(int j=1;j<=k;j++){

            char c;

            cin>>c;

            s+=c;

        }

        insert(s);

    }

    for(int i=1;i<=m;i++){

        int k;

        string s;

        cin>>k;

        for(int j=1;j<=k;j++){

            char c;

            cin>>c;

            s+=c;

        }

        printf("%d\n",query(s));

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[前缀统计|前缀统计]] 🏠 [[00-刷题理模型]] ➡️ [[字典树|字典树]]