字典树

用来求字符串前缀的，给你n个字符串和m次询问，在这m次询问中，有多少个字符串的前缀为t。

getnum(char x) 映射规则

有的题目可能不只是包含字母，还包含了数字，此时我们就要定义各字符的编号。

int getnum(char x) 
{ 
 if(x>='A' and x<='Z') 
     return x-'A'; 
 else if( x>='a' and x<='z' ) 
      return x-'a'+26; 
   return x-'0'+52;
 }

insert(char str[]) 插入字符串

这个思想感觉和链式前向星差不多的感觉，让p一直走这个字符串的位置，如果这个孩子的位置不存在就新建节点。然后再走向这个节点，每走一次就有一个字符串经过这个位置，那么cnt[x]++。

void insert(char str[]) //插入前缀 
{ int p=0,len=strlen(str); 
  for(int i=0;i<len;i++) 
  {  int c=getnum(str[i]); //获取到映射规则，应该是第c位 
     if( !t[p][c] ) //如果当前位置没有节点 
         t[p][c]=++idx; //建立节点 
     p=t[p][c];
     //移动到下一层节点 
    cnt[p]++; //经过该节点的前缀+1 }
 }

find(char str[])

查询经过str这个字符串路径的字符串有多少个。 就一直往这条路径走下去，如果走到某一个节点后，发现下个节点不存在，那么直接return 0； 反之一直走下去，最后返回这个节点的经过次数就可以了return cnt[x]； 代码其实和insert差不多

int find(char str[])		//查询函数，去查询有多少个字符有str前缀的
{
  int p=0,len=strlen(str);  
  for(int i=0;i<len;i++)    //与插入时的理论差不多
  {
    int c=getnum(str[i]);
    if( !t[p][c] )     //特判，如果当前位置没有插入过字符，没有字符经过这个前缀，必须必须必须直接返回0
       return 0;
    p=t[p][c];    //反之，有这个前缀，指针移动
  }
  return cnt[p];
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+12;
int T,q,n,t[N][65],cnt[N],idx;
//T 为大样例  q为询问次数 n为插入的字符个数 t为字典树数组 cnt为该前缀出现次数  idx为下标
char s[N];
int getnum(char x)
{
  if(x>='A' and x<='Z')
    return x-'A';
  else if( x>='a' and x<='z' )
    return x-'a'+26;
  return x-'0'+52;
}
//映射规则，A~Z,a~z，0~9；
void insert(char str[]) //插入前缀
{
  int p=0,len=strlen(str);
  for(int i=0;i<len;i++)
  {
    int c=getnum(str[i]);  //获取到映射规则，应该是第c位
    if( !t[p][c] )  //如果当前位置没有节点
        t[p][c]=++idx;   //建立节点
    p=t[p][c];    //移动到下一层节点
    cnt[p]++;    //经过该节点的前缀+1
  }
}
int find(char str[])		//查询函数，去查询有多少个字符有str前缀的
{
  int p=0,len=strlen(str);  
  for(int i=0;i<len;i++)    //与插入时的理论差不多
  {
    int c=getnum(str[i]);
    if( !t[p][c] )     //特判，如果当前位置没有插入过字符，没有字符经过这个前缀，必须必须必须直接返回0
       return 0;
    p=t[p][c];    //反之，有这个前缀，指针移动
  }
  return cnt[p];
}
int main(){
  scanf("%d",&T);
  while(T--)
  {
    for(int i=0;i<=idx;i++)
      for(int j=0;j<=65;j++)
        t[i][j]=0;
    for(int i=0;i<=idx;i++)
      cnt[i]=0;
    idx=0;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
      scanf("%s",s);
      insert(s);
    }
    for(int i=1;i<=q;i++)
    {
      scanf("%s",s);
      printf("%d\n",find(s));
    }
  }
}