поиск в массиве строк начинающихся с подстроки / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / поиск в массиве строк начинающихся с подстроки

9 сообщений из 9, страница 1 из 1

поиск в массиве строк начинающихся с подстроки

#34947182

tipoc

Гость

Всех приветствую! У меня вопрос:
есть массив отсортированных по возрастанию строк. Нужно найти концевые индексы подмассива элементов, начинающихся с подстроки.

Пример: есть массив

Код: plaintext

array = {"абсурд", "авангард", "август", "авось", "агава", "аура"}

, подстрока

Код: plaintext

from="ав"

. В данном случае

Код: plaintext

подмассив = {"авангард", "август", "авось"}

(т.е. строки, начинающиеся с "ав"). Концевые индексы: начальный индекс = 1, конечный индекс = 3 (индексация массива идет с нуля).

Как лучше реализовать данный алгоритм? (чтобы был не слишком сложный и работал относительно быстро). Кол-во строк в массиве может достигать десятки тысяч. Если что, язык программирования Java. Ссылки на статьи приветствуются. :)

...

Рейтинг:

0 / 0

18.11.2007, 04:48

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947183

ErV

Участник

Сообщения: 1 702

Рейтинг: 0 / 0

tipoc wrote:

> Как лучше реализовать данный алгоритм?
Отталкиваться от двоичного поиска.
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4

...

Рейтинг:

0 / 0

18.11.2007, 04:56

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947185

tipoc

Гость

ErV> Как лучше реализовать данный алгоритм?
Отталкиваться от двоичного поиска.
Пытался, но в голову не приходит явное решение. Да и двоичный поиск хорош только для точного поиска. Может есть другие решения?

...

Рейтинг:

0 / 0

18.11.2007, 05:02

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947187

Restavraciya

Участник

Сообщения: 5 141

Рейтинг: 0 / 0

> Если что, язык программирования Java
Если что, свалить в ado recordset и искать в нем доступными средствАми ;-)

...

Рейтинг:

0 / 0

18.11.2007, 06:37

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947188

teras

Гость

tipoc wrote:
> Автор: tipoc
>> ErV
>>> Как лучше реализовать данный алгоритм?
>> Отталкиваться от двоичного поиска.
>
> Пытался, но в голову не приходит явное решение. Да и двоичный поиск
> хорош только для точного поиска.

Это не так. Его вполне можно использовать и в этом случае.
Я тут как-то описывал свое видение алгоритма
тут .
Возможно, поможет составить нужный алгоритм. Для поиска интервала, его
придется применять дважды - для поиска первого элемента и последнего
элемента. Кроме того, результаты первого поиска могут сузить интервал
для второго.

> Может есть другие решения?
Если не преобразовывать массив или не строить доп.структур, то пожалуй
нет. Если можно преобразовывать, то я бы подумал в первую очередь о
trie. все-таки в нем время поиска пропорционально длине искомой строки
(в данном случае - за два шага).
Posted via ActualForum NNTP Server 1.4

...

Рейтинг:

0 / 0

18.11.2007, 07:06

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947275

ErV

Участник

Сообщения: 1 702

Рейтинг: 0 / 0

tipoc wrote:

> Да и двоичный поиск хорош только для точного поиска.
Варианты:
1) проводим поиск дважды. В первом случае ищем элемент, который
начинается с нужной строки, и имеет перед ним строку "меньше" него.
Вторым поиском ищем элемент, который начинается с нужной подстроки, но
содержит после него подстроку "больше" него. Это можно задать в
критерии сравнения.
2) Тупо находим любой элемент, начинающийся с нужной подстроки и ищем
первый и последний элемент такого типа последовательным перебором от
найденного элемента. (в сторону начала и в сторону конца массива).
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4

...

Рейтинг:

0 / 0

18.11.2007, 12:20

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34947548

tipoc

Гость

ErV1) проводим поиск дважды. В первом случае ищем элемент, который
начинается с нужной строки, и имеет перед ним строку "меньше" него.
Вторым поиском ищем элемент, который начинается с нужной подстроки, но
содержит после него подстроку "больше" него. Это можно задать в
критерии сравнения.
Так и сделаю. Спасибо!

...

Рейтинг:

0 / 0

18.11.2007, 19:14

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34956325

Liventsev Andrey

Участник

Сообщения: 10

Рейтинг: 0 / 0

в Яве делается элементарно:

Код: plaintext

1.
2.
3.
4.
5.

Set result = new HashSet();
if( stringArray[i].length()>=s.length() &&  stringArray[i].substring( 0 ,s.length()- 1 ).equals(s) ){
    if( stringArray[i].substring( 0 ,s.length()- 1 ).equals(s) ){
        result.add( stringArray[i] );
     }
}

где stringArray это массив стрингов - String[]. s - искомая подстрока.

...

Рейтинг:

0 / 0

21.11.2007, 18:10

| Ответить | Цитировать | Написать

поиск в массиве строк начинающихся с подстроки

#34956820

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

tipocВсех приветствую! У меня вопрос:
есть массив отсортированных по возрастанию строк. Нужно найти концевые индексы подмассива элементов, начинающихся с подстроки.
.....
Как лучше реализовать данный алгоритм? (чтобы был не слишком сложный и работал относительно быстро). Кол-во строк в массиве может достигать десятки тысяч. Если что, язык программирования Java. Ссылки на статьи приветствуются. :)

Насколько я понимаю, вы кодите словарь.

Если объем словаря укладывается в границы свободной памяти ОС, то можно хранить все слова в массиве. Более продвинутое решение - подумать над коллекцией, которая быстро ищет "ключи в диапазоне" (например BTree). Не забывайте, что время инициализации массива - тоже важно. Если он должен быть персистентным то так или иначе вы его будете хранить во внешнем файле. Значит надо подумать о том, как он будет загружатся и как (когда) выгружатся, чтобы не быть балластом для ОС и других приложений.

В остальных случаях - рулит встраиваемая СУБД. Попробуйте прикрутить JavaDB или HSQL. Обратите внимание на индексы по текстовым полям, индексно-организованные таблицы, индексы по функции. Это может пригодится.

Всего.

...

Рейтинг:

0 / 0

21.11.2007, 22:19

| Ответить | Цитировать | Написать

9 сообщений из 9, страница 1 из 1

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&fpage=153&tid=1345693]:	0ms
get settings:	6ms
get forum list:	21ms
check forum access:	3ms
check topic access:	3ms
track hit:	49ms
get topic data:	8ms
get forum data:	2ms
get page messages:	41ms
get tp. blocked users:	1ms
others:	259ms

total:	393ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы