Re: Divide a list of string into substrings

http://qs321.pair.com?node_id=11118297

in reply to Divide a list of string into substrings

I think that I understand your requirements.

Given a set of strings.

Split each string into a list of substrings of at least three character each
From the set of all possible decompositions, select the one with the lowest score

Scoring a decomposition

Form the set of all the substrings (Keep only one of each duplicated substrings)
Sum the lengths of all the substrings in that set.
The score is that sum plus twice the number of substrings in the set.

I suspect that execution time of any solution would be exponential in the total number of characters.

Bill

Comment on Re: Divide a list of string into substrings

Replies are listed 'Best First'.
Re^2: Divide a list of string into substrings by Anonymous Monk on Jun 21, 2020 at 09:18 UTC
Hi Bill You understood the problem. Your way guarantees the best result, but as you wrote for a longer list you will get an issue with the runtime. What I am looking for is: Some ideas to do the job, to get a good result (low score) in a reasonable runtime even for longer lists and strings. Knowing that this fast approach might not give the optimal solution (lowest score).	[reply]

In Section Seekers of Perl Wisdom