1

I've got bunch of strings with variable-length prefixes (or postfixes - I can always revert them) as follows:

0155555555
523455555555
755555555
...
87129999999999999
119999999999999
09119999999999999

The prefixes are random and of unknown length (could be 0 too). The common part are not fixed digit (used it above as an illustration only for clarity) but arbitrary set of digits, for examples 928349283642762376 - here first 4 letters is prefix and the rest is common. Each common sequence appears multiple but unknown number of types.

What I'm looking for is an algorithm which will take bunch of strings like that (strings from clusters with different common substring are intermixed) and output common parts. I'm pretty sure somebody already solved this problem and there's an algorithm named after some brilliant guy - the problem is that I don't know this name and all attempts to find it failed so far.

More realistic example:

6253283642762376
12283642762376
112263754347656838
09877283642762376
2283642762376
09863754347656838
663754347656838
177712668888889

Should produce 3 clusters 283642762376, 63754347656838 and 177712668888889 as common substrings for 4, 3 and 1 string correspondingly.

My attempts to find the solution revealed either too dumb brute-force algorithms or way too complex machine-learning with Levenstein distance and sequence alignment. So, what shall I be looking for actually?

Update: pardon, forgot to mention that the minimal length of common substring used for clustering should be either algorithm parameter or calculated greedily - the longest match wins.

  • 1
    I don't think the problem is specified well enough to produce an answer. You need at least one other rule. For example, 91234,81234,88234,99994. You could classify as 2x1234,1x234,1x4; or 3x234,1x4; or 4x4. Amongst others. – Alex Jul 16 '15 at 15:09
  • What is the minimum size of a cluster? – User Jul 16 '15 at 19:03
  • The minimum cluster is single string - like 177712668888889 in the example above. – god Jul 17 '15 at 13:24

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.