题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<string.h>
using namespace std;
const int N =1e5+10;
int M;
int son[N][26], cnt[N], idx;//下标是0的点,既是根结点,又是空结点
char str[N];
void insert(string 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(string str)
{
int p = 0;
for(int i = 0;str[i];i++)
{
int u = str[i] - 'a';
if(!son[p][u])
{
return 0;
}
p = son[p][u];
}
return cnt[p];
}
int main()
{
cin >> M;
while(M--)
{
string op;
string str;
cin >> op;
if(op == "I")
{
cin >> str;
insert(str);
}
else
{
cin >> str;
cout << query(str) << endl;
}
}
return 0;
}