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

Question

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

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

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

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

Должен вернуться:

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

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

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

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

Должен вернуться:

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

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

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

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

Mykeul

Answer 1

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

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

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

Возможно, вы также захотите поискать реализации PHP "diff". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/

Answer 2

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

Хорошо, теперь мы подошли к вопросу о том, как сравнить две строки, чтобы получить строку с подстановочными знаками.

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

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

Удачи!