算法题（195）：点名

审题：

本题需要我们判断字符串的查询状态，并根据不同查询状态输出不同的结果

思路：
方法一：字典树

本题可以先将所有字符串存储到某一种数据结构中，然后此数据结构可以完成字符串次数与字符串本身的关系绑定（key—value类型），我们查看字符串出现次数

（1）初次查询：为1输出OK，然后将次数改为-1

（2）没有该字符串：为0输出WRONG

（3）重复查询：为-1就输出REPEAT

解题：
 

#include<iostream>
using namespace std;
const int N = 5e5 + 10;
int e[N], tr[N][26];
int n, m;
int idx;
void insert(string& s)
{int cur = 0;for (auto ch : s){int path = ch - 'a';if (tr[cur][path] == 0) tr[cur][path] = ++idx;cur = tr[cur][path];}e[idx]++;
}
void inquire(string& s)
{int cur = 0;for (auto ch : s){int path = ch - 'a';if (tr[cur][path] == 0){cout << "WRONG" << endl;return;}cur = tr[cur][path];}if (e[cur] == 1)//初次点名{e[cur] = -1;cout << "OK" << endl;}else if(e[cur] == -1)//重复点名{cout << "REPEAT" << endl;}else//无此名字{cout << "WRONG" << endl;}
}
int main()
{//数据插入字典树cin >> n;for (int i = 1; i <= n; i++){string s; cin >> s;insert(s);}//数据查询与结果输出cin >> m;for (int i = 1; i <= m; i++){string s; cin >> s;inquire(s);}return 0;
}

（1）tr数组中N的取值：tr数组行变量的个数是总字符个数决定的

总字符个数 = 字符串个数 * 单字符串的最大字符数 = 1e4 * 50 = 5e5

（2）本题不需要判断字符串前缀，只需要记录字典树中哪个节点是字符串的终点，所以我们只需要用end数组即可

（3）出现WRONG的情况有两种：

其一是在进行查询中间就发现没有该字符串

其二是查询字符串是存储的字符串的前缀，此时for循环可以正常结束，但是该字符串其实是不存在的，需要特殊判断

---

样例如下

1

ab

1

a

由于a是ab的前缀，所以for循环可以正常结束，而此时三种情况都可能出现，所以我们要用

if——else if ——else的语句块进行判断。

P2580 于是他错误的点名开始了 - 洛谷