Trouver les caractères communs tableau de chaînes, dans le bon ordre

Question

J'ai passé des jours de travail sur une fonction pour obtenir les caractères communs dans un tableau de chaînes, dans l'ordre, pour créer un caractère générique.

Voici un exemple pour expliquer mon problème. J'ai fait environ 3 fonctions, mais j'ai toujours un bug quand la position absolue de chaque lettre est différente.

Supposons que "+" est le "char joker":

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

doit retourner:

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

Dans cet exemple, la chose la plus délicate est que $array[2] comme 1 caractère plus que d'autres.

Autre exemple:

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

doit retourner:

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

Dans cet exemple, les parties délicates sont les suivantes:
- caractères à répétition, comme 1 -> 11 dans le « supprimer "partie, et c -> cc dans la partie commune
- Le caractère" 2 "dans $ array [2] & [3] dans la partie" à supprimer "n'est pas dans la même position
- Le caractère "1" à la fin de la dernière chaîne

J'ai vraiment besoin d'aide car je ne trouve pas de solution à cette fonction et c'est une partie essentielle de mon application.

Merci à l'avance, ne hésitez pas à poser des questions, je répondrai aussi vite que possible.

Mykeul

Answer 1

Code principal:
Etape 1: Trie les chaînes par la longueur, la plus courte à la plus longue, dans un tableau []
Etape 2: Comparer la chaîne dans le tableau [0] et tableau [1] pour obtenir temp_wildcard
$ étape 3: Comparer la chaîne dans le tableau [2] avec temp_wildcard $ pour créer de nouveaux $ temp_wildcard
étape 4: Continuer la comparaison de chaque chaîne avec temp_wildcard de $ - le dernier joker $ est votre temp_wildcard de $

OK, maintenant nous sommes jusqu'au problème de la façon de comparer deux chaînes pour retourner votre chaîne générique.

Code de sous-programme: Comparez les chaînes caractère par caractère, en remplaçant les valeurs génériques par des caractères génériques lorsque la comparaison ne correspond pas.

Pour gérer le problème de différentes longueurs, exécutez cette comparaison une fois de plus pour chaque caractère dont la deuxième chaîne est plus longue avec un décalage. (Comparez string1 [x] à string2 [x + offset].) Pour chaque chaîne renvoyée, comptez le nombre de caractères génériques. Le sous-programme doit retourner la réponse avec le moins de caractères génériques possible.

Bonne chance!

Answer 2

Semble que vous voulez créer quelque chose comme expression régulière sur ensemble de chaînes par exemple. Cela pourrait être tout à fait Tricki en général. Nous avons trouvé ce lien, ne sais pas si elle est pertinente: 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'autre part, si vous avez besoin d'un seul caractère générique spécifique qui signifie « 0 ou plusieurs caractères », alors il devrait être beaucoup plus facile. Levenshtein distance algorithme calcule la similarité entre les 2 chaînes. Normalement, seul le résultat est nécessaire, mais dans votre cas, les lieux de différences sont importants. Vous devez également l'adapter pour N chaînes.

Je recommande donc d'étudier cet algorithme et nous espérons que vous aurez des idées comment résoudre votre problème (au moins vous aurez un peu de pratique avec des algorithmes de texte et la programmation dynamique).

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

Vous pouvez également rechercher des implémentations de PHP de "diff". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/