Найти общие символы в массиве строк, в правильном порядке

Question

Я провел дни, работая над функцией, чтобы получить общие символы в массиве строк в правильном порядке, чтобы создать подстановочный знак.

Вот пример, чтобы объяснить мою проблему. Я сделал около 3 функций, но у меня всегда есть ошибка, когда абсолютная позиция каждой буквы отличается.

Давайте предположим, что «+» является «подстановочные символ»:

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

Если вернуться:

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

В этом примере, сложная вещь, что $array[2], как один символ больше, чем другие.

Другой пример:

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

Если вернуться:

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

В этом примере, хитрые части:
- Повторяющиеся символы, такие как 1 -> 11 в «удалить "part и c -> cc в общей части
- Символ« 2 »в $ array [2] & [3] в разделе« удалить »не находится в том же положении
- Символ «1» в конце последней строки

Мне очень нужна помощь, потому что я не могу найти решение этой функции, и это основная часть моего приложения.

Заранее спасибо, не стесняйтесь задавать вопросы, я отвечу как можно быстрее.

Mykeul

Answer 1

Главный код:
Шаг 1: Сортировка строк по длине кратчайшего к длинной, в массив []
Шаг 2: Сравнение строки в массиве [0] и массив [1], чтобы получить $ temp_wildcard
Шаг 3: сравнение строки в массиве [2] с $ temp_wildcard создать новый $ temp_wildcard
Шаг 4: Продолжайте сравнивать каждую строку с $ temp_wildcard - последний $ подстановочные ваш $ temp_wildcard

ОК, так что теперь мы вплоть до проблемы сравнения двух строк для возврата строки подстановки.

Код подпрограммы: Сравнение строк по символам, подстановка подстановочных знаков в возвращаемое значение, если сравнение не соответствует.

Чтобы справиться с проблемой разной длины, запустите это сравнение дополнительное время для каждого символа, чтобы вторая строка была длиннее со смещением. (Сравните string1 [x] с строкой2 [x + смещение].) Для каждой возвращаемой строки подсчитывайте количество подстановочных символов. Подпрограмма должна вернуть ответ с наименьшим количеством подстановочных знаков.

Удачи вам!

Answer 2

Кажется, вы хотите создать что-то вроде регулярного выражения из множества примеров строк. Это может быть довольно трюки вообще. Найдено эту ссылку, не уверен, если это отношение: 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

С другой стороны, если вам нужен только один конкретный подстановочные означающий «0 или более символов», то это должно быть намного проще. Levenshtein distance алгоритм вычисляет сходство между двумя строками. Обычно требуется только результат, но в вашем случае важны места различий. Вам также необходимо адаптировать это для N строк.

Поэтому я рекомендую изучить этот алгоритм, и, надеюсь, вы получите некоторые идеи, как решить вашу проблему (по крайней мере, вы получите некоторую практику с текстовыми алгоритмами и динамическим программированием).

Heres алгоритм в PHP: _http: //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#PHP

Вы можете также искать для PHP реализаций "дифф". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/