CODEWITHSUNDEEP
pythonstring
julienfr112
julienfr112

Reputation: 2137

Algorithm or and python implementation of getting a minimal list of prefix suffix of a list

I'm trying to find an algorithme that with a list of word, give the minimum list of prefix and suffix such that every word is the concatanation of a prefix and a suffix.

ex :

[banano, ananas, applenas, appleno, neo, neas]

=> [bana,anan,e, apple] [as no]

Is that possible ?

Upvotes: 1

Views: 260

Answers (1)

Jirka Hanika
Jirka Hanika

Reputation: 13549

The solution is not uniquely defined. For example, for language [aa, ab, bb] the solution might be either [a, b] [a, b], or [aa, ab, bb] and empty string.

The problem can be understood as an instance of the minimum string cover problem (just assume that each string starts with a mandatory begin-string character, and ends with another mandatory end-string character. The allowed covering dictionary would then consist of all prefixes and all suffixes of all words in the input language.

The general string cover problem is NP-hard, but as soon as you impose the rule (here implied by the appearance of begin-string and end-string characters) that only a fixed maximal number of strings (here, two) may cover any given input string, it becomes polynomially solvable.

Here is a C++ implementation of a solver of minimum string cover problems.

Upvotes: 4

Related Questions