自闭

数组模拟trie

1.trie存的是字符串，从s[0],开始存

• 二维数组，第一维记录节点的编号,第二维的索引代表字符，数组值存 节点编号（26个指针，指向下一个节点）

  const int maxn=1e6;
  int tot = 0;//全局变量，记录所以节点的数量
  int endp[maxn];//每个节点编号都可能作为一个字符串的末尾,
  void inserts(string s){
      int ch,p=0;//p=0，代表从空的根节点开始插入值
      for (int i=0;i<s.size();i++) {
          ch = s[i] - 'a';
          if ( trie[p][ch] == 0 )//说明该节点没有走过，给它编号 
              trie[p][ch] = ++tot;
          p = trie[p][ch];//p到了下一节点
      }
      endp[p] += 1;//标记该节点为字符串的末尾，或者记录信息
  }
  int query(string s){
      int p=0;
      for (int i=0;i<s.size();i++ ) {
          // p是编号，字符理解为指针的方向
          p = trie[p][s[i] - 'a'];//第2个字符节点的编号
          if ( !p ) //该字符没有节点编号，说明没有存
              return false;
      }
      return true;
  }

2. trie存数字，按二进制位从高位到低位存，(题目数据会小于第32位符号位的)

   int tot = 0;
   const int maxn=1e5+10;
   int trie[maxn][2];
   void insertn(int num) {
       int p=0;
       for (int i=30;i>=0;i--) {
           int ch = (num>>i) & 1;
           if ( !trie[p][ch] ) trie[p][ch] = ++tot;
           p = trie[p][ch];
       }
   }
   // query()根据题目的需要写
   bool query(int num) {
       int p=0;
       for (int i=30;i>=0;i--) {
           int ch = (num>>i) & 1;
           if ( trie[p][ch] ) p = trie[p][ch];
           else return false;
       }
       return true;
   }

例题：字符串的前缀统计

• trie的建树，查询

  #include <iostream>
  #include <string>
  using namespace std;
  const int maxn=1e6+10;
  int tot = 0;
  int trie[maxn][26];
  int endnum[maxn];
  void inserts(string s){
      int p=0,ch;
      for (int i=0;i<s.size();i++) {
          ch = s[i]-'a';
          if (!trie[p][ch]) trie[p][ch]=++tot;
          p = trie[p][ch];
      }
      ++endnum[p];//以编号p结尾的字符串 个数+1
  }
   
  int query(string s){
      int p=0;
      int ans = 0;//统计字符串前缀的个数
      for (int i=0;i<s.size();i++) {
          // endnum[0] 不可能作为string的节点
          p = trie[p][s[i]-'a']; // p点时该字符的下一个字符的地址，
          if ( !p ) break; // p==0 没有下一个字符
          ans += endnum[p];
      }
      return ans;
  }
  char ch[maxn];
  string s;
  int main() {
  //    freopen("a.txt","r",stdin);
      int n,m;
      scanf("%d%d",&n,&m);
      for (int i=0;i<n;i++) {
          scanf("%s",ch);
          s=ch;
          inserts(s);
      }
      for (int i=0;i<m;i++) {
          scanf("%s",ch);
          s=ch;
          printf("%d\n",query(s));
      }
      return 0;
  }