指针trie 33pts RE求调
查看原帖
指针trie 33pts RE求调
450246
Eleveslaine楼主2023/1/27 12:04
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
class TrieNode
{
    public:
        TrieNode* son[maxn];
        bool end;
        TrieNode()
        {
            memset(son,0,sizeof(son));
            end=0;
        }
        ~TrieNode()
        {
            for(int i=0;i<maxn;++i)
                delete son[i];
        }
};
TrieNode* root;
map <string,int> idt;
int cnt=0,n,sum=0;
string s;
inline int id(const string &s)
{
    if(idt[s]!=0)
        return idt[s];
    else
        return idt[s]=++cnt;
}
inline int insert(const vector<string> &vec)
{
    TrieNode* p=root;
    int ans=0;
    for(auto s:vec)
    {
        int ID=id(s);
        if(p->son[ID]==NULL)
        {
            ++ans;
            p->son[ID]=new TrieNode;
        }
        p=p->son[ID];
    }
    p->end=1;
    return ans;
}
int main()
{
    root=new TrieNode;
    cin >> n;
    while(n--)
    {
        vector <string> vec;
        cin >> s;
        s+='/';
        for(int i=1,last=1;i<s.length();++i)
            if(s[i]=='/')
            {
                vec.push_back(s.substr(last,i-last));
                last=i+1;
            }
        cout << (sum+=insert(vec)) << endl;
    }
    return 0;
}

指针真tm的好用(咬牙切齿)。

2023/1/27 12:04
加载中...