Arrange rows for maximum overlap

Question

Let's say I have this rowset:

strings = {'qqq', 'eqq', 'qqw', 'www', 'qww', 'wwe', 'eee', 'eeq', 'wee', 'qwe'} 

How to write an algorithm that arranges strings so that they overlap as much as possible? I already know that one way to build them is as follows:

 qww www wwe wee eee eeq eqq qqq qqw qwe 

However, I found the result above using brute force solution. Is there a smarter way to do this?

Answer 1

This is called the shortest task of a super string and NP complete.

You may be interested in the approaches in the article Application Algorithms for the Shortest General Superstring Problem of Jonathan Turner .