Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree

【 Topic link 】

ybt 1337：【 example 3-2】 Word search tree
Luogu P5755 [NOI2000] Word search tree

【 Topic test site 】

1. Dictionary tree

【 Their thinking 】

solution 1： Dictionary tree

Dictionary tree template questions . Learn about dictionary tree in csdn search “ Dictionary tree ” or “tire Trees ”.
This question says that the total length of the document does not exceed 32K,$32KB=32\ast 1024B=32768B$, The total number of characters will not exceed 33000 individual . Therefore, the total number of node pools is set to 33000.

【 Solution code 】

solution 1： Dictionary tree

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    
    int child[26];//child[i]: Character is a i+'A' The address of the child node  
};
Node node[33000];
int p, root;// Root node root The address is 0, From address 1 Start assigning nodes  
void insert(string s)// Insert words into the dictionary tree s 
{
    
    int pf = root;// The address of the currently concerned node  
    for(int i = 0; i < s.length(); ++i)
    {
    
        if(node[pf].child[s[i]-'A'] == 0)
            node[pf].child[s[i]-'A'] = ++p;// Assign new nodes  
        pf = node[pf].child[s[i]-'A'];//pf Point to the next node  
    }
}
int getNodeNum(int r)// Get the root node address as r Node number of the tree of  
{
    
    int sum = 1;// I am 1 Nodes  
    for(int i = 0; i < 26; ++i)// Statistics r Number of subtree nodes  
    {
    
        if(node[r].child[i] > 0)
            sum += getNodeNum(node[r].child[i]);
    }
    return sum;
}
int main()
{
    
    string s;
    while(cin >> s)
        insert(s);// Put the word s Insert dictionary tree  
    cout << getNodeNum(root);// Get the node number of the whole tree  
    return 0;
}