【字典树】点名

什么是字典树？

题意：有n个字符串，然后有m次询问，每次询问问你存不存在字符串p 如果该名字正确且是第一次出现，输出 OK，如果该名字错误，输出 WRONG，如果该名字正确但不是第一次出现，输出 REPEAT。

分析：用字典树存下n个字符串，并只在字符串结尾的时候打上标记1。然后m次询问的时候就按照正常字典树方式走，并且记录新的数组u代表是否访问过这个位置。

1. 如果返回返回0那么就是不存在这个字符串。
2. 如果返回1那么就是存在这个字符串存在并且研究访问过了。
3. 如果返回2那就是没有访问过。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int n,m,t[N][60],cnt[N],u[N],idx;
void inster(char s[])
{
  int len=strlen(s);
  int p=0;
  for(int i=0;i<len;i++)
  {
    int c=s[i]-'a';
    if( !t[p][c] )
      t[p][c]=++idx;
    p=t[p][c];
  }
  cnt[p]++;
}
int find(char s[])
{
  int len=strlen(s);
  int p=0;
  for(int i=0;i<len;i++)
  {
    int c=s[i]-'a';
    if( t[p][c]==0 )
      return 0;
    p=t[p][c];
  }
  if( cnt[p]==0 ) return 0;
  if( u[p] ) return 1;
  u[p]++;
  return 2;
}
int main(){
  char s[N];
  cin>>n;
  while(n--)
  {
    scanf("%s",s);
    inster(s);
  }
  cin>>m;
  while(m--)
  {
    cin>>s;
    int x=find(s);
    if( x==0 ) cout<<"WRONG\n";
    else if(x==1) cout<<"REPEAT\n";
    else cout<<"OK\n";
  }

}