I want to find the longest possible sequence of words that match the following rules:

• Each word can be used at most once
• All words are Strings
• Two strings sa and sb can be concatenated if the LAST two characters of sa matches the first two characters of sb.

In the case of concatenation, it is performed by overlapping those characters. For example:

• sa = "torino"
• sb = "novara"
• sa concat sb = "torinovara"

For example, I have the following input file, "input.txt":

novara

torino

vercelli

ravenna

napoli

liverno

messania

noviligure

roma

And, the output of the above file according to the above rules should be:

torino

novara

ravenna

napoli

livorno

noviligure

since the longest possible concatenation is:

torinovaravennapolivornovilligure

Can anyone please help me out with this? What would be the best data structure for this?