Encontrar caracteres comunes en una matriz de cadenas, en el orden correcto

Question

Pasé días trabajando en una función para obtener caracteres comunes en una matriz de cadenas, en el orden correcto, para crear un comodín.

Aquí hay un ejemplo para explicar mi problema. Hice alrededor de 3 funciones, pero siempre tengo un error cuando la posición absoluta de cada letra es diferente.

Asumamos "+" es el "char comodín":

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

debe devolver:

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

En este ejemplo, lo difícil es que $array[2] como 1 carácter más que otros.

Otro ejemplo:

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

debe devolver:

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

En este ejemplo, las partes difíciles son:
- caracteres que se repiten, tales como 1 -> 11 en el "para eliminar "parte, yc -> cc en la parte común
- El" 2 "char en $ array [2] & [3] en la parte" para eliminar "no está en la misma posición
- El "1" char al final de la última cadena

Realmente necesito ayuda porque no puedo encontrar una solución a esta función y es una parte principal de mi aplicación.

Gracias de antemano, no dude en hacer preguntas, le responderé lo más rápido posible.

Mykeul

Answer 1

Código principal:
Paso 1: ordenar cadenas de longitud, más corto al más largo, en una matriz []
Paso 2: Comparación de cadena en serie [0] y la matriz [1] para obtener $ temp_wildcard
paso 3: comparación de cadena en serie [2] con $ temp_wildcard para crear nueva $ temp_wildcard
paso 4: Continuar la comparación de cada cadena con $ temp_wildcard - el último $ comodín es su temp_wildcard $

OK, así que ahora estamos hasta el problema de cómo comparar dos cadenas para devolver su cadena comodín.

Código de subrutina: Compara las cadenas carácter por carácter, sustituyendo los caracteres comodín en el valor de retorno cuando la comparación no concuerde.

Para resolver el problema de las diferentes longitudes, ejecute esta comparación un tiempo extra para cada carácter que la segunda cuerda es más larga con un desplazamiento. (Compare string1 [x] con string2 [x + offset].) Para cada cadena devuelta, cuente el número de caracteres comodín. La subrutina debe devolver la respuesta con el menor número de caracteres comodín.

¡Buena suerte!

Answer 2

Parece que desea crear algo así como una expresión regular de juego de cuerdas ejemplo. Esto podría ser bastante tricki en general. Encontrado este enlace, no está seguro de si es relevante: 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

Por otro lado, si sólo se necesita un comodín específica "significa 0 o más caracteres", entonces debería ser mucho más fácil. El algoritmo Levenshtein distance calcula la similitud entre 2 cadenas. Normalmente solo se necesitan resultados, pero en su caso los lugares de diferencias son importantes. También necesita adaptar esto para N strings.

Así que recomiendo estudiar este algoritmo y espero que obtenga algunas ideas de cómo resolver su problema (al menos obtendrá algo de práctica con algoritmos de texto y programación dinámica).

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

Es posible que desee también para buscar las implementaciones de PHP "diff". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/