如题,我使用一份错误的代码通过了这道题,但是这是一个假做法。
例如,这么一个数据:
1
aabbcc
3
aab
aab
aab
我的输出是:
WRONG
REPEAT
REPEAT
这显然是不合题意的。
问题出现在 trie 树的查询中。我的代码对于这种数据是错误的:存在字符串 T,如果 T 名字错误,但是是某一个正确名字的前缀,而且这个数据被查询到至少两次。
在我的代码中:第一次查询返回 0,之后返回 -1。也就是第二次查询 T 返回的答案均为错误答案,但是这样仍然通过了这一道题。
所以我希望可以加强这道题的数据。
// 这是我的提交记录
// https://www.luogu.com.cn/record/167481169
const int M = 5e5 + 10;
int son[M][30], cnt[M], idx;
char str[55];
void insert(char 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(char 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];
}
int res = cnt[p];
cnt[p] = -1;
return res;
}
int main()
{
int n, m;
scanf("%d", &n);
while (n --) {
scanf("%s", str);
insert(str);
}
scanf("%d", &m);
while (m --) {
scanf("%s", str);
int res = query(str);
if (res > 0) printf("OK\n");
if (res == 0) printf("WRONG\n");
if (res == -1) printf("REPEAT\n");
}
} // 忽略了其余部分