XiYuJing|文章:字符串统计

[[ slide_text ]]

[[item.c]]

字符串统计

发布时间：2022年10月08日 作者：靖华来源：XiYuJing

算法 C++ Trie

# 字符串统计
维护一个字符串集合，支持两种操作：

1. `I x` 向集合中插入一个字符串 x；
2. `Q x` 询问一个字符串在集合中出现了多少次。

共有 N 个操作，输入的字符串总长度不超过 10<sup>5</sup>，字符串仅包含小写英文字母。

#### 输入格式

第一行包含整数 NN，表示操作数。

接下来 NN 行，每行包含一个操作指令，指令为 `I x` 或 `Q x` 中的一种。

#### 输出格式

对于每个询问指令 `Q x`，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

#### 数据范围

1≤N≤2∗10<sup>4</sup>

#### 输入样例：

```
5
I abc
Q abc
Q ab
I ab
Q ab
```

#### 输出样例：

```
1
0
1
```
> 题目来源于AcWing

## 代码
```c++
#include<iostream>
using namespace std;
typedef long long ll;
const int N =1e5+10;
int cot[N],p[N][26],idx=0;
void inset(string s)
{
    int x = 0; 
    for(int i=0;i<s.size();i++)
    {
        int u = s[i]-'a';
        if(!p[x][u])p[x][u]=++idx;
        x=p[x][u];
    }
    cot[x]++;
}
int query(string s)
{
    int x = 0;
    for(int i=0;i<s.size();i++)
    {
        int u = s[i] - 'a';
        if(!p[x][u])return 0;
        x=p[x][u];
    }
    return cot[x];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string f,s;
        cin>>f>>s;
        if(f=="I"){
            inset(s);
        }
        else{
            cout<<query(s)<<endl;
        }
    }
}
```
## 原理
#### 重点在插入的方法,这个用到的存储方法和跟链表的链式向前星原理一样，P数组一维存的是当前的字母，二维存的是下个字母所在的位置，cot用来标记结尾。

你觉得文章怎么样

已浏览 97 次，0 条评论