To be clear, I didn't hear of this in any particular venue, and so can't point you to one.

Two variants that I can bring you:

  1. String spitting

    Given a string (sequence of elements), and a function that takes a substring and returns a score/penalty. Overall score is the product of scores of chosen split.

    Find the optimal way to split the string into consecutive, non-overlapping substring to maximize the score.

  2. String folding

    Given the same as (1).

    Also given a function that takes two substring and an edge (head-head, head-tail, etc.) specifying how the substrings will connect, returns a score.

    Find the optimal way to "fold" the string. Any two "elbows" (or folding points) can be made to touch. No length limitations (substring length is not geometrically motivated).

I haven't been able to find mentions of "optimizing string splitting" online. So I'm doubting it might be more specialized than I'd thought.

  • 1
    $\begingroup$ The 'string splitting' operation on a string is the same as deciding on line-breaks in a piece of text. The objective function is usually global in that case, and not local as you describe here. There is quite some literature on line-breaking, perhaps searching for "line breaking algorithm" or something similar will help. $\endgroup$
    – Discrete lizard
    May 17 '20 at 14:35
  • $\begingroup$ Can you clarify how the individual scores of the sub-strings in (1) are combined to a total score? Is it simply a summation, or do you take a sum of squares or something more involved? $\endgroup$
    – Discrete lizard
    May 17 '20 at 14:39
  • $\begingroup$ @Discretelizard - Line breaking looks very interesting, thanks! ; I added a bit on the total score. You can choose something else if it's interesting to handle. Mine is simply the product of the probabilities of the chosen split. $\endgroup$
    – MNael
    May 18 '20 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.