Найдите общие символы в массиве строк в правильном порядке
Я провел дни, работая над функцией, чтобы получить общие символы в массиве строк, в правильном порядке, создать подстановочный знак.
Вот пример для объяснения моей проблемы. Я сделал приблизительно 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" символ в $array [2] и [3] в, "для удаления" части не находится в том же положении
- "1" символ в конце последней строки
Я действительно нуждаюсь в помощи, потому что я не могу найти решение этой функции, и это - основная часть моего приложения.
Заранее спасибо, задайте вопросы, отвечу я максимально быстро.
Mykeul
2 ответа
Основной код:
Шаг 1: Сортировать строки по длине, кратчайшие дольше, в массив []
Шаг 2: Сравните строку в массиве [0] и массив [1], чтобы получить $ temp_wildcard
Шаг 3: Сравните строку в массиве [2] с $ temp_wildcard для создания новых $ temp_wildcard
Шаг 4: Продолжайте сравнивать каждую строку с $ temp_wildcard - последний $ Fundcard - это ваша $ temp_wildcard
ok, поэтому теперь мы к проблеме, как сравнить две строки, чтобы вернуть вашу строку подстановки.
Подпрограмма: Сравните Charits-Charace-персонажа, подставляя подстановочные знаки в ваше возвращаемое значение, когда сравнение не совпадает.
Чтобы справиться с проблемой разных длин, выполните это сравнение дополнительное время для каждого символа, что вторая строка дольше с смещением. (Сравните string1 [x] на string2 [x + offset].) Для каждой возвращенной строки подсчитайте количество символов подстановки. Подпрограмма должна вернуть ответ с наименьшим количеством символов подстановочных знаков.
Удачи!
Кажется, что вы хотите создать что-то вроде регулярного выражения из набора примерных строк. Это может быть довольно Tricki в целом. Нашел эту ссылку, не уверен, если это актуально: http://scholar.google.com/scholar?hl=en&rlz=1B3GGGL_ENEEE351EE351&q=%22Gegular%20Expression%20by%20example%22&oq=&um=1&ie=utf-8&sa=n&tab=UTF-8&sa=n&tab=ws
С другой стороны Если вам нужен только один конкретный подстановочный знак «0 или более персонажей», то ему должно быть намного проще. Расстояние Левенштейна алгоритм вычисляет сходство между 2 строками. Обычно требуется только результат, но в вашем случае места различий важны. Вам также необходимо адаптировать это для N строк.
Поэтому я рекомендую изучить этот алгоритм и, надеюсь, вы получите некоторые идеи, как решить вашу проблему (по крайней мере, вы получите некоторую практику с текстовыми алгоритмами и динамическим программированием).
Алгоритм вот в PHP: _http: //en.wikibooks.org/wiki/algorithm_implementation/strings/levenshtein_distance#phpenshtein_distance#php
Возможно, вы также захотите искать реализации PHP «Diff». http://paulbutler.org/Чахивы/a-simple-diff-algorithm-in-php/