I've got bunch of strings with variable-length prefixes (or postfixes - I can always revert them) as follows:0155555555523455555555755555555...8712999999999999911999999999999909119999999999999The 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:62532836427623761228364276237611226375434765683809877283642762376228364276237609863754347656838663754347656838177712668888889Should 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.
clustering of strings with variable-length prefixes
algorithms;strings;string matching