Cod sursa(job #3152988)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 27 septembrie 2023 15:45:13
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin ("trie.in");
ofstream fout ("trie.out");

const int NMAX=27;

class Trie{
    public:
    Trie* sons[NMAX];
    int frecv;
    int ind;

    Trie()
    {
        frecv=0;
        ind=0;
        for(int i=0;i<=25;i++)
            sons[i]=NULL;
    }
};

void insert_value(Trie* &node,string &s,int poz)
{
    if(poz==s.length())
        return ;
    if(node->sons[s[poz]-'a']==NULL)
        node->sons[s[poz]-'a']=new Trie();
    node->sons[s[poz]-'a']->frecv++;
    if(poz==s.length()-1)
        node->sons[s[poz]-'a']->ind++;
    insert_value(node->sons[s[poz]-'a'],s,poz+1);
}

void remove_value(Trie* &node,string &s,int poz)
{
    if(poz==s.length())
        return ;
    if(node->sons[s[poz]-'a']==NULL)
        return ;
    node->sons[s[poz]-'a']->frecv--;
    if(poz==s.length()-1)
        node->sons[s[poz]-'a']->ind--;
    remove_value(node->sons[s[poz]-'a'],s,poz+1);
}

int get_freq(Trie* node,string &s,int poz)
{
    if(poz==s.length())
        return 0;
    if(node->sons[s[poz]-'a']==NULL)
        return 0;
    if(poz==s.length()-1)
        return node->sons[s[poz]-'a']->ind;
    return get_freq(node->sons[s[poz]-'a'],s,poz+1);
}

int lcp(Trie* node,string &s,int poz,int lvl)
{
    if(poz==s.length())
        return lvl;
    if(node->sons[s[poz]-'a']==NULL)
        return lvl;
    if(node->sons[s[poz]-'a']->frecv==0)
        return lvl;
    return lcp(node->sons[s[poz]-'a'],s,poz+1,lvl+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    Trie* node=new Trie();
    int type;
    string s;
    while(fin>>type>>s)
    {
        if(type==0)
           insert_value(node,s,0);
        else if(type==1)
            remove_value(node,s,0);
        else if(type==2)
            fout<<get_freq(node,s,0)<<"\n";
        else
            fout<<lcp(node,s,0,0)<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}