加密信息
题目 加密信息
思路分析
M串和N串长度并没有严格大小之分，所以存在两种情况，一种是N串是M串的子串，另一种是M串是N串的子串
对于这两种子串，我们都需要经过Trie树某一个点之后的字符串数量，以及以这个点为结尾的字符串数量
注意 它这的读入是带空格的 110这个字符串 成1 1 0读入 所以用char读入 拼成string
代码实现
#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;
}
💬 评论