Ciao a tutti,
ho di recente provato a risolvere Friendly Note utilizzando un suffix trie, purtroppo esso occupa O(|S|^2) di spazio totalizzando un triste 50/100. Mi chiedevo se esistesse qualche tecnica oscura per farlo stare nei limiti del problema.
Se qualcuno fosse interessato, lascio il mio codice:
struct node{
map<char,node*> children;
};
int dispute(string N, string S)
{
node* root = new node;
node* curr;
for(int i=S.size(); i--;)
{
curr = root;
for(int j=i; j<S.size(); j++)
{
if(curr->children.find(S[j]) == curr->children.end())
curr->children[S[j]] = new node;
curr = curr->children[S[j]];
}
}
int seq = 1;
curr = root;
for(int i=0; i<N.size();)
{
if(curr->children.find(N[i]) != curr->children.end())
curr = curr->children[N[i++]];
else
{
curr = root;
seq++;
}
}
return seq;
}
P.S.: tornerĂ mai MathJax?
