A (probably mathematical?) question regarding strings
Difference between en1 and en2, changed 131 character(s)
I have 2 questions in mind, just out of curiousity :). They both consider [tries](https://en.wikipedia.org/wiki/Trie) (not compressed). Also note — by a trie's size I'm not considering its root (even though, it does not matter for the purpose of this problem).

1) For some 2 natural numbers $N$ and $K$ (suppose $K \leq N$), what is the maximal size of a trie that can be achieved if you take some string $S$ of length $N$, with the size of its language (number of distinct characters it can contain) being $K$, and insert into the trie all its suffixes (so, a suffix trie)?↵

For instance, if $N = 2, K = 2$, we can form the string "ab", which makes the trie of size 3. On the other hand, if $N = 10, K = 1$, the only string we can form is "aaaaaaaaaa" which makes the trie size 10.↵

2) How do you form such a string with maximal trie size? An algorithm or an idea, both are acceptable.↵

Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Noam527 2018-01-12 18:22:34 131
en1 English Noam527 2018-01-12 18:18:27 832 Initial revision (published)