I have a problem and I need an algorithm to solve it.
I could not find it and I do not know if the problem is NP-Hard.
The problem is: I have several sequences of symbols. I want to merge them into a single sequence, where all symbols of the original sequences are included keeping the original order of the symbols. Duplicated symbols that came from different sequences should be removed. The resulting sequence must be the smallest sequence that is possible.
If one of the sequences is "abc", the resulting sequence must be *a*b*c*, where * is a sequence of 0 or more symbols. If the input sequences are 'abc' and 'cba', the output must be 'abcba', 'c' is included once and the *a*b*c* and *c*b*a* property is kept.
abcde xbcaf axdaf
A way how it is merged:
a-bcde-- -xbc--af ax--d-af
Multiple outputs is possible, 'abcd' and 'cba' will result in 'abcdba', 'abcbda' or 'abcbad'. I will need just one output, any output is valid, if its length is the smallest lenght that is possible.