# Friendly Note un po' troppa memoria

**URL:** <https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801>\
**Category:** Aiuto\
**Created:** [24 Settembre 2017, 5:09pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801 "2017-09-24T17:09:32Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [24 Settembre 2017, 5:09pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/1 "2017-09-24T17:09:32Z")

</div>

Ciao a tutti,  
ho di recente provato a risolvere [Friendly Note](https://cms.di.unipi.it/#/task/ioit_neighborly/statement) 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:

```auto
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?

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [25 Settembre 2017, 11:52am UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/2 "2017-09-25T11:52:37Z")

</div>

non devi usare un suffix trie.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [25 Settembre 2017, 12:18pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/3 "2017-09-25T12:18:39Z")

</div>

Ok sono molto triste, qualche aiutino?

---

<div class="post-metadata">

**Author:** ![rossimelthomas](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/d26b3c/32.png) [@rossimelthomas](https://forum.olinfo.it/u/rossimelthomas)\
**Post date:** [25 Settembre 2017, 12:19pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/4 "2017-09-25T12:19:33Z")

</div>

come mi è stato suggerito da erolm  
suffix array

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [25 Settembre 2017, 12:35pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/5 "2017-09-25T12:35:16Z")

</div>

Neanche suffix array

---

<div class="post-metadata">

**Author:** ![rossimelthomas](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/d26b3c/32.png) [@rossimelthomas](https://forum.olinfo.it/u/rossimelthomas)\
**Post date:** [25 Settembre 2017, 12:40pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/6 "2017-09-25T12:40:00Z")

</div>

Te cosa hai usato?  
Erolm ha salvato gli indici con un suffix array ed ha funzionato

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [25 Settembre 2017, 12:52pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/7 "2017-09-25T12:52:01Z")

</div>

Ho usato un semplice suffix tree

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [25 Settembre 2017, 12:55pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/8 "2017-09-25T12:55:06Z")

</div>

E quale sarebbe la differenza? 😅

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [26 Settembre 2017, 6:53pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/9 "2017-09-26T18:53:45Z")

</div>

Dopo innumerevoli tentativi sono finalmente riuscito a ottenere 100/100 utilizzando un suffix tree, grazie comunque per l’aiuto.

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [27 Settembre 2017, 2:18pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/10 "2017-09-27T14:18:19Z")

</div>

Tra Suffix Trie e Suffix Tree nessuna, probabilmente @lukecavabarrett intendeva che serve una versione “compressa” dell’albero.

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [27 Settembre 2017, 2:38pm UTC](https://forum.olinfo.it/t/friendly-note-un-po-troppa-memoria/4801/11 "2017-09-27T14:38:47Z")

</div>

Suffix tree e suffix trie sono differenti  
Il suffix tree è la compressione del suffix trie