Trie Ref:OI Wiki


示例代码:

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }
  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

题目: P2580 于是他错误的点名开始了
代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;

char s[60];
int n, m, ch[N][26], tag[N], tot = 1;

int main() {
    cin>>n;

    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        int u = 1;
        for (int j = 1; s[j]; ++j) {
          int c = s[j] - 'a';
         if (!ch[u][c])
          ch[u][c] = ++tot;
          u = ch[u][c];
       }
       tag[u] = 1;
    }

    scanf("%d", &m);

    while (m--) {
        scanf("%s", s + 1);
        int u = 1;
        for (int j = 1; s[j]; ++j) {
            int c = s[j] - 'a';
            u = ch[u][c];
            if (!u)
                break;  // 不存在对应字符的出边说明名字不存在
        }
    if (tag[u] == 1) {
        tag[u] = 2;
        puts("OK");
    } else if (tag[u] == 2)
        puts("REPEAT");
    else
        puts("WRONG");
    }

  return 0;
}