采用树的形式存储字符串,实现快速插入和查找操作
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-7
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 80000;
struct node
{
int son[26];
bool isend;
} t[N];
int cnt = 1;
void Insert(char *s)
{
int now = 0;
for (int i = 0; s[i]; i++)
{
int ch = s[i] - 'a';
if (t[now].son[ch] == 0)
t[now].son[ch] = cnt++;
now = t[now].son[ch];
int len = strlen(s);
if (i == len - 1)
t[now].isend = true;
}
}
bool Find(char *s)
{
int now = 0;
for (int i = 0; s[i]; i++)
{
int ch = s[i] - 'a';
if (t[now].son[ch] == 0)
return false;
now = t[now].son[ch];
}
if (t[now].isend == false)
return false;
return true;
}
int main()
{
char s[51];
int n;
cin >> n;
while (n--)
{
scanf("%s", s);
Insert(s);
}
int m;
cin >> m;
while (m--)
{
scanf("%s", s);
bool res = Find(s);
if (res)
puts("True");
else
puts("False");
}
return 0;
}