题解 P2580 【于是他错误的点名开始了】

· · 题解

qwq！为什么！木有非结构体非指针的题解怎么阔以！所以， 我来辽~咻咻咻~ 题面 来分析， 我们可以先建一棵树，来存储整个名单， 然后再判断

for (int i = 1; i <= n; i++) {
        root = 0;
        cin >> ch;
        int len = strlen (ch);
        for (int j = 0; j < len; j++) {
            int nu = ch[j] - 'a';
            if (!tr[root][nu]) tr[root][nu] = ++tot;
            root = tr[root][nu];
        }
        f[root] = 1;
    }

这一段代码是具体的存储的过程， f数组用来存储整个单词被用过几次。可以自己分析品味一哈， 这个root变量到最后存储的其实就是您目前存储的单词的最后一个字母， 也就是代表了这个单词的结束， 所以直接用root这个变量来表示这个单词被用过几次即可。

for (int j = 0; j < len; j++) {
            int nu = ch[j] - 'a';
            if (!tr[root][nu]) {
                printf ("WRONG\n");
                break;
            }
            root = tr[root][nu];
            if (j == len - 1 && f[root] == 2) printf ("REPEAT\n");
            if (j == len - 1 && f[root] == 1) f[root] = 2,printf ("OK\n"); 
        }

查询， 根据题目意思， 按要求输出， 并且要注意换行， 大写之类的细节性问题。要注意， 每一次判断到最后的时候， 判断是否是被用过， 没有被用过的， 需要标记表示应经用过了

再就是root这个变量每次都要更新（我真的调了好久）

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char ch[800000];
int n, m, tr[8000000][26], s, root, tot, f[8000000];
int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        root = 0;
        cin >> ch;
        int len = strlen (ch);
        for (int j = 0; j < len; j++) {
            int nu = ch[j] - 'a';
            if (!tr[root][nu]) tr[root][nu] = ++tot;
            root = tr[root][nu];
        }
        f[root] = 1;
    }
    scanf ("%d", &m);
    for (int i = 1; i <= m; i++) {
        root = 0;
        cin >> ch;
        int len = strlen (ch);
        for (int j = 0; j < len; j++) {
            int nu = ch[j] - 'a';
            if (!tr[root][nu]) {
                printf ("WRONG\n");
                break;
            }
            root = tr[root][nu];
            if (j == len - 1 && f[root] == 2) printf ("REPEAT\n");
            if (j == len - 1 && f[root] == 1) f[root] = 2,printf ("OK\n"); 
        }
    }
    return 0;
}