Ho un sacco di stringhe con prefissi di lunghezza variabile (o postfixes - Posso sempre ripristinarli) come segue:
0155555555
523455555555
755555555
...
87129999999999999
119999999999999
09119999999999999
I prefissi sono casuali e di lunghezza sconosciuta (potrebbe essere anche 0). La parte comune non è una cifra fissa (usata sopra come un'illustrazione solo per chiarezza) ma una serie arbitraria di cifre, per esempio 928349283642762376 - qui le prime 4 lettere sono prefisso e il resto è comune. Ogni sequenza comune appare in numero multiplo ma sconosciuto di tipi.
Quello che sto cercando è un algoritmo che prenderà un mucchio di stringhe come quella (stringhe di cluster con sottostringhe comuni differenti sono mescolate) e produrrà parti comuni. Sono abbastanza sicuro che qualcuno abbia già risolto questo problema e che ci sia un algoritmo che prende il nome da un ragazzo geniale - il problema è che non conosco questo nome e tutti i tentativi di trovarlo fallito finora.
Esempio più realistico:
6253283642762376
12283642762376
112263754347656838
09877283642762376
2283642762376
09863754347656838
663754347656838
177712668888889
Dovrebbe produrre 3 cluster 283642762376, 63754347656838 e 177712668888889 come sottostringhe comuni per 4, 3 e 1 stringa in modo corrispondente.
I miei tentativi di trovare la soluzione hanno rivelato algoritmi di forza bruta troppo stupidi o un apprendimento macchina troppo complesso con la distanza di Levenstein e l'allineamento di sequenza. Quindi, cosa dovrei cercare in realtà?
Aggiornamento: perdonare, dimentica di menzionare che la lunghezza minima della sottostringa comune utilizzata per il clustering deve essere un parametro dell'algoritmo o calcolata avidamente - la vincita più lunga vince.