We have all the possible 3-grams of lower case letters (A = {a, b, c, ..., z}):
A3 = A × A × A =
{
(a, a, a),
(a, a, b),
(a, a, c),
...,
(a, a, z),
(b, a, a),
...,
(z, z, y),
(z, z, z),
}
|A3| = 263 = 17576
If we try to merge aaa with bbb we have to append bbb to the end of aaa, because they don't overlap:
merge(aaa, bbb) = aaabbbIf we merge aaa with aab we can create a smaller string:
merge(aaa, aab) = aaab
In the best case, if we manage to always do a second kind of merge, we will be extending the resulting string by 1 character. There are 17576 triplets, so there can be at most 17575 single character extensions. This will result in 17575 + 3 = 17578 characters string.
In the worst case, we will append all of the 3-grams to each other, thus creating a 17576 * 3 = 52728 characters string.
How to combine all of them to get the total string of the minimum length?
Picture to attract people :)
Where is this problem from?
It is my problem inspired by Symbolic Sequence.
For me it looks like the problem is pretty foundational, but I couldn't google neither the problem nor the solution. The closest problem that I found is the problem of assembling human genome, but again it is pretty different from what I am looking for.
I believe this is exactly what you want.
Thank you!
But how did you google it? :)
I just happen to know some old problem that is named after this sequence and asks to find exactly it.
Эхх что за времена пошли два русских друг с другом на английском общаются.
UPD И у самого страна Америка )))))))
По нику не так просто понять кто есть кто =)