I'm trying solve problem Jukebox from ICPC Latin America Regional 2006. You can read the problem statement and submit solutions here. Please, read the problem statement to understand all the details, but here is a summary:
Basically you are given N songs, each song with a title and an artist. There is at most 30 songs, 6 artists and the strings are at most 30 characters long. For each song, you can decide if you keep or hide the artist. The task is to find the optimal way of keeping/hiding artists such that the sum total of the lengths of the songs' golden strings is minimized. A song's golden string is any shortest substring of either the song's title or artist (if the artist is not hidden) such that it is not substring of any other song. In other words, when you type a song's golden string, only that song is matched. There is always at least one valid solution.
My approach. You can find my code below.
The idea: Since showing two or more times the same artist doesn't help, basically we have two options for each artist: hide it completely or reveal it just once. So I thought that backtracking would be good enough to explore all these possibilities since there is at most 6 artists. Then, to find out the golden string for each song, I came up with the following idea: we can concatenate all songs and titles in a single string, build a suffix array from the concatenation,
