Есть определенный (большой) набор строк. Некоторые из них частично совпадают, например:
"ВасяПупкин", "ПупкинВася", "Оля+Вася=XXX", "Петя".
Как выделить в отдельный набор совпадающие подстроки данных строк, чтобы получилось два набора: из совпадающих подстрок и "уникальных остатков"? Т.е. в нашем примере это должны быть:
"Вася", "Пупкин"
— набор1,
"Оля+", "=XXX", "Петя"
— набор2.
Таким образом уменьшится объем данных (исходный набор большой, и в нем много частично совпадающих строк), а элементы полученных массивов будут использованы как подстроки для поиска в "больших" строках (которые зараннее неизвестны).
Задача поиска — выявить вхождение какой-любо из строк исходного набора, полностью или частично. Важно не то, какая именно строка из исходного набора найдется, а найдется ли какая-нибудь строка или ее часть
из данного набора вообще. Пример:
Поиск строк в строке
"ИвановВасяТраЛаЛа"
должен увенчаться упехом для данного исходно набора строк. Тоже самое для строки:
"Маша+Юра=XXX"
Здравствуйте, AvaLANche, Вы писали:
ALA>Есть определенный (большой) набор строк. Некоторые из них частично совпадают, например:
ALA>"ВасяПупкин", "ПупкинВася", "Оля+Вася=XXX", "Петя".
ALA>Как выделить в отдельный набор совпадающие подстроки данных строк, чтобы получилось два набора: из совпадающих подстрок и "уникальных остатков"? Т.е. в нашем примере это должны быть:
ALA>"Вася", "Пупкин"
— набор1,
ALA>"Оля+", "=XXX", "Петя"
— набор2.
ALA>Таким образом уменьшится объем данных (исходный набор большой, и в нем много частично совпадающих строк), а элементы полученных массивов будут использованы как подстроки для поиска в "больших" строках (которые зараннее неизвестны).
ALA>Задача поиска — выявить вхождение какой-любо из строк исходного набора, полностью или частично. Важно не то, какая именно строка из исходного набора найдется, а найдется ли какая-нибудь строка или ее часть из данного набора вообще. Пример:
ALA>Поиск строк в строке
ALA>"ИвановВасяТраЛаЛа"
ALA>должен увенчаться упехом для данного исходно набора строк. Тоже самое для строки:
ALA>"Маша+Юра=XXX"
Может это покажется странным, но мне эта задача чем-то напомнила алгоритмы сжатия на основе LZ88. Попробуй копнуть в сторону алгоритма LZW. Например, можно по ходу построения словаря считать количество вхождения каждого префикса, а затем на основе этих частот разбивать исходные строки на подстроки.
С уважением Михаил Копачев
... << RSDN@Home 1.1.4 @@subversion >>