Быстрый поиск подстроки

@Fixer_84 · Регистрация: 30.04.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте! С помощью какого класса (контейнера) можно осуществить быстрый поиск подстроки в строке (за O(1)), например? Какие методы лучше использовать? Очень жду ответ.

@xoraxax · 28.01.2018, 21:47

думаю, вот это https://www.youtube.com/watch?v=SZFe3m1DV1A

@КОП · 28.01.2018, 22:23

Fixer_84, неужели так сложно выложить ссылку на задачу? может правила форума запрещают?

Java
1
2
3
4
5
6
7
8
9
10
11
12
    public static void main(String[] args) throws IOException {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        String s1 = bi.readLine();
        String s2 = bi.readLine();
        int index = s1.indexOf(s2);
        StringBuilder sb = new StringBuilder(10000000);
        while (index >= 0) {
            sb.append(index).append(" ");
            index = s1.indexOf(s2, index + 1);
        }
        System.out.println(sb.toString());
    }

@Fixer_84 · 28.01.2018, 22:32 **[ТС]**

КОП, спасибо Вам! Все получилось.

Сообщение от КОП

неужели так сложно выложить ссылку на задачу? может правила форума запрещают?

P.S. да, это не по правилам

@КОП · 28.01.2018, 22:38

Не по теме:

Сообщение от Fixer_84

да, это не по правилам

жуть какая! тогда вопросов нет)
ну или можно кстати копипастнуть текст, чтоб кавычками прогуглить можно было

@Fixer_84 · 28.01.2018, 22:42 **[ТС]**

КОП, еще раз спасибо. Неудобно спрашивать почему у вас получилось быстрее. Надеюсь, мы с моим преподавателем сможем разобраться. Все, что знаю, что append() работает быстрее чем обычная конкатенация...

@КОП · 28.01.2018, 22:48

Сообщение от Fixer_84

Неудобно спрашивать

так мы для этого тут и собрались)

Сообщение от Fixer_84

Все, что знаю, что append() работает быстрее чем обычная конкатенация...

дело даже не столько в append, сколько в одном вызове sysout. Хотя наверняка не скажу, не замерял
Так же не работало без capacity (1000000 в конструкторе). То есть если билдер не выделит сразу много памяти, то на перевыделение уйдет много времени.
Ну и BufferReader тоже быстрее сканера. Сканер бы на доли секуды запорол 9й вроде, уже не помню точно.

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337

	Быстрый поиск подстроки 28.01.2018, 01:18. Показов 3750. Ответов 25 Метки нет (Все метки) Здравствуйте! С помощью какого класса (контейнера) можно осуществить быстрый поиск подстроки в строке (за O(1)), например? Какие методы лучше использовать? Очень жду ответ. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	28.01.2018, 21:47
	думаю, вот это https://www.youtube.com/watch?v=SZFe3m1DV1A 1

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	28.01.2018, 22:42 [ТС]
	КОП, еще раз спасибо. Неудобно спрашивать почему у вас получилось быстрее. Надеюсь, мы с моим преподавателем сможем разобраться. Все, что знаю, что append() работает быстрее чем обычная конкатенация... 0

Быстрый поиск подстроки

Решение