ch 1(データ構造編)——Trieツリー

1.自然言語記述辞書ツリーに挿入されたすべてのシーケンスの各文字を番号付けし、シーケンスの最後にマークします.本来文字列を格納する用途に加えて、Trieツリー自体の考え方で他の用途がある.
2.コード記述タイトル:Acwing.835 Trieツリー文字列統計タイトルリンク

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN=1e5+10;

int n,son[MAXN][26],cnt[MAXN],idx;//son[i][j]=x，i Trie    j     ,x  j          ;
//cnt              ,                    
char str[MAXN];

void Insert(char str[])
{
     
    int p=0;
    for(int i=0;str[i];i++){
     
        int u=str[i]-'0';
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

void Query(char str[])
{
     
    int p=0;
    for(int i=0;str[i];i++){
     
        int u=str[i]-'0';
        if(!son[p][u]){
     
            cout<<0<<endl;
            return;
        }
        p=son[p][u];
    }
    cout<<cnt[p]<<endl;
}

int main(void)
{
     
    cin>>n;
    
    for(int i=0;i<n;i++){
     
        char op[2];
        cin>>op>>str;
        
        if(op[0]=='I')
            Insert(str);
        else
            Query(str);
        
    }
    
    return 0;
}

タイトル:Acwing.143最大異種または対題リンク

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN=1e5+10,M=31*MAXN;
typedef  unsigned long long ULL;

//Trie             ，             
int n,son[M][2],idx,s[MAXN];

void Insert(int x)
{
     
    int p=0;
    for(int i=30;i>=0;i--){
     //          2^(31)，                 
        int u=x>>i&1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
}

int search(int x)
{
     
    int p=0,res=0;
    for(int i=30;i>=0;i--){
     
        int u=x>>i&1;
        if(son[p][!u]){
     //       ，                 
            p=son[p][!u];//  ，        
            res=res*2+1;//        1
        }else{
     
            p=son[p][u];//   ，          
            res*=2;//     0
        }
    }
    return res;
}

int main(void)
{
     
    cin>>n;
    
    for(int i=1;i<=n;i++){
     
        cin>>s[i];
        Insert(s[i]);
    }
    
    int ans=0;
    for(int i=1;i<=n;i++)//             ，    
        ans=max(ans,search(s[i]));
    cout<<ans<<endl;
    
    return 0;
}