Trova caratteri comuni nella stringa di stringhe, nell'ordine corretto

Question

Ho trascorso giorni a lavorare su una funzione per ottenere caratteri comuni in una serie di stringhe, nell'ordine corretto, per creare un carattere jolly.

Ecco un esempio per spiegare il mio problema. Ho fatto circa 3 funzioni, ma ho sempre un bug quando la posizione assoluta di ogni lettera è diversa.

Supponiamo "+" è il "char jolly":

Array(
0 => '48ca135e0$5', 
1 => 'b8ca136a0$5', 
2 => 'c48ca13730$5', 
3 => '48ca137a0$5'); 

deve restituire:

$wildcard='+8ca13+0$5'; 

In questo esempio, la cosa difficile è che $array[2] come 1 carattere più di altri.

Altro esempio:

Array(
0 => "case1b25.occHH&FmM", 
1 => "case11b25.occHH&FmM", 
2 => "case12b25.occHH&FmM", 
3 => "case20b25.occHH&FmM1"); 

deve restituire:

$wildcard='case+b25.occHH&FmM+'; 

In questo esempio, le parti difficili sono:
- caratteri ripetere, come ad esempio 1 -> 11 in "per eliminare "parte e c -> cc nella parte comune
- Il carattere" 2 "in $ array [2] & [3] nella parte" per eliminare "non è nella stessa posizione
- Il carattere "1" alla fine dell'ultima stringa

Ho davvero bisogno di aiuto perché non riesco a trovare una soluzione a questa funzione ed è una parte principale della mia applicazione.

Grazie in anticipo, non esitate a fare domande, risponderò il più velocemente possibile.

Mykeul

Answer 1

codice principale:
Fase 1: ordinare le stringhe di lunghezza, corta alla più lunga, in una matrice []
Fase 2: Confronta stringa in array [0] e la matrice [1] per ottenere $ temp_wildcard
fase 3: Confronta stringa in array [2] con $ temp_wildcard per creare nuovi $ temp_wildcard
fase 4: Continua a confronto ogni stringa con $ temp_wildcard - l'ultimo $ jolly è il vostro $ temp_wildcard

OK, quindi ora siamo giù al problema di come confrontare due stringhe per restituire la stringa jolly.

Codice sottoprogramma: Confrontare le stringhe carattere per carattere, sostituendo i caratteri jolly nel valore restituito quando il confronto non corrisponde.

Per gestire il problema di diverse lunghezze, eseguire questo confronto un tempo aggiuntivo per ogni carattere che la seconda stringa è più lunga con un offset. (Confrontare string1 [x] a stringa2 [x + offset].) Per ogni stringa restituita, contare il numero di caratteri jolly. La subroutine dovrebbe restituire la risposta con il minor numero di caratteri jolly.

Buona fortuna!

Answer 2

Sembra si vuole creare qualcosa di simile a un'espressione regolare di serie di esempi di stringhe. Questo potrebbe essere abbastanza complesso in generale. Trovato questo link, non so se sia rilevante: http://scholar.google.com/scholar?hl=en&rlz=1B3GGGL_enEE351EE351&q=%22regular%20expression%20by%20example%22&oq=&um=1&ie=UTF-8&sa=N&tab=ws

D'altra parte, se avete bisogno di un solo carattere jolly specifica che significa "0 o più caratteri", allora dovrebbe essere molto più facile. L'algoritmo Levenshtein distance calcola la somiglianza tra 2 stringhe. Normalmente è necessario solo il risultato, ma nel tuo caso i punti di differenza sono importanti. Devi anche adattare questo per N stringhe.

Quindi mi raccomando di studiare questo algoritmo e spero che tu abbia qualche idea su come risolvere il tuo problema (almeno avrai un po 'di pratica con algoritmi testuali e programmazione dinamica).

algoritmo Heres in PHP: _http: //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#PHP

Si potrebbe desiderare anche per la ricerca di implementazioni PHP di "diff". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/