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.