Cod sursa(job #2735828)

Utilizator armigheGheorghe Liviu Armand armighe Data 2 aprilie 2021 21:04:01
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
char s[22];
int k;

struct trie
{
    int sum,fv;
    vector<int>v;
};
vector<trie>a;
vector<int>gol;

void add(int x,int i)
{
    a[x].sum++;
    if(s[i+1]=='\0')
        a[x].fv++;
    else
    {
        if(a[x].v.size()==0)
        {
            for(int j=0;j<=25;j++)
                a[x].v.push_back(0);
        }
        if(a[x].v[s[i+1]-'a']==0)
            a[x].v[s[i+1]-'a']=++k,a.push_back({0,0,gol});
        add(a[x].v[s[i+1]-'a'],i+1);
    }
}

void del(int x,int i)
{
    a[x].sum--;
    if(s[i+1]=='\0')
        a[x].fv--;
    else
        del(a[x].v[s[i+1]-'a'],i+1);
   // if(a[x].sum==0)
   //     a[x].v.clear();
}

int ap(int x,int i)
{
    if(s[i+1]=='\0')
        return a[x].fv;
    if(a[x].v.size()==0||a[x].v[s[i+1]-'a']==0)
        return 0;
    return ap(a[x].v[s[i+1]-'a'],i+1);
}

int pref(int x,int i)
{
    if(a[x].sum==0)
        return max(i-1,0);
    if(s[i+1]=='\0')
        return i;
    if(a[x].v.size()==0||a[x].v[s[i+1]-'a']==0)
        return i;
    return pref(a[x].v[s[i+1]-'a'],i+1);
}

int main()
{
    int p;
    a.push_back({0,0,gol});
    while(f>>p)
    {
        f>>(s+1);
        if(p==0)
            add(0,0);
        else
        if(p==1)
            del(0,0);
        else
        if(p==2)
            g<<ap(0,0)<<'\n';
        else
            g<<pref(0,0)<<'\n';
    }
    return 0;
}