Поиск массива строк в массиве строк

@OlegNN52 · Регистрация: 10.07.2019

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

Господа и товарищи!
Проблема такая. Нужно написать прогу, которая ищет в массиве строк массив строк. Главное, чтобы быстро... Или, говоря другими словами, в одной матрице ищет другую матрицу.Например,
ab
ab
ищется в матрице
abcdab
abbabc
abbaba
Результат: 3.
Написал две проги, но они считают очень медленно. Кто знает, есть ли какие алгоритмы, ускоряющие процесс? Мои идеи были таковы. Применяю построчно алгоритм Кнута-Морриса-Пратта, сравниваю индексы вхождения подстрок. Но при достаточно больших массивах это очень-очень медленно... Кто сталкивался? Накидайте идей, пли-ииз...

@Aviz__ · 11.07.2019, 08:02

OlegNN52, из твоего примера, как мне думается, правильный ответ должен быть 2, а не 3. т.к. полные искомые матрицы либо первые символы, первой - второй строки и предпоследние второй - третей, либо первые символы, второй - третьей строки, и также предпоследние второй - третей.
приведи код одной из программ, чтобы было ясно о каких матрицах идет речь, пока кажется, что все строковые.

@OlegNN52 · 11.07.2019, 15:29 **[ТС]**

Aviz__, Считается именно так, как я написал. Перекрывающиеся матрицы тоже все в счет. Считаю вот так:

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
for (int i=0; i<lineText-linePattern+1; i++){
            List<Integer> lst=kmpListSearch(text[i],pattern[0]);
            int sum=0;
            if(!lst.isEmpty()){
                if(lineText==1){
                    return lst.size();
                }
                for (int e=0; e<lst.size();e++){
 
                    for(int j=1; j<linePattern;j++){
                        List<Integer> lstSec=kmpListSearch(text[i+j],pattern[j]);
 
                        for(int k=0; k<lstSec.size(); k++){
                            if(lst.get(e)==lstSec.get(k)){
                                sum++;
 
                            }
                        }
                        if(sum==linePattern-1){
                            res++;
                            sum=0;
                            break;
                        }
 
 
                    }
 
 
                }
            }
        }
        return res;
 
 
    }

@Aviz__ · 11.07.2019, 15:40

Не по теме:

OlegNN52, Бро, код программ нужно обрамлять тегами JAVA одна из кнопок выше

не согласен, что перекрывающиеся считать верно, но хз, ты сам решаешь.

@xoraxax · 11.07.2019, 15:43

OlegNN52, тебя никто не понимает, какие матрицы, что ты считаешь?

@OlegNN52 · 11.07.2019, 19:35 **[ТС]**

Есть два массива строк. Один - шаблон(pattern), надо найти сколько раз он встречается в другом массиве - text. Можно рассматривать как массивы строк, можно как матрицы - без разницы. Фрагмент кода, собственно подсчёт. Вполне рабочий, но очень медленный. Все вхождения шаблона 100 на 100 в тексте 1500 на 1500 считал больше часа...
В коде kmpListSearch реализует алгоритм Кнута-Морриса-Пратта. Считываю индексы вхождения первой подстроки шаблона в первой строке текста, затем построчно остальные строки шаблона, при совпадении всех - плюсую к результату. Всё незамысловато...
В общем, уже есть мысли как сделать лучше, но не факт...

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
for (int i=0; i<lineText-linePattern+1; i++){
            List<Integer> lst=kmpListSearch(text[i],pattern[0]);
            int sum=0;
            if(!lst.isEmpty()){
                if(lineText==1){
                    return lst.size();
                }
                for (int e=0; e<lst.size();e++){
 
                    for(int j=1; j<linePattern;j++){
                        List<Integer> lstSec=kmpListSearch(text[i+j],pattern[j]);
 
                        for(int k=0; k<lstSec.size(); k++){
                            if(lst.get(e)==lstSec.get(k)){
                                sum++;
 
                            }
                        }
                        if(sum==linePattern-1){
                            res++;
                            sum=0;
                            break;
                        }
 
 
                    }
 
 
                }
               
        }
        return res;
 
 
    }

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@OlegNN52 0 / 0 / 0 Регистрация: 10.07.2019 Сообщений: 6

	Поиск массива строк в массиве строк 10.07.2019, 22:29. Показов 1469. Ответов 5 Метки алгоритм, массив, матрицы, поиск в тексте (Все метки) Господа и товарищи! Проблема такая. Нужно написать прогу, которая ищет в массиве строк массив строк. Главное, чтобы быстро... Или, говоря другими словами, в одной матрице ищет другую матрицу.Например, ab ab ищется в матрице abcdab abbabc abbaba Результат: 3. Написал две проги, но они считают очень медленно. Кто знает, есть ли какие алгоритмы, ускоряющие процесс? Мои идеи были таковы. Применяю построчно алгоритм Кнута-Морриса-Пратта, сравниваю индексы вхождения подстрок. Но при достаточно больших массивах это очень-очень медленно... Кто сталкивался? Накидайте идей, пли-ииз... 0

@Aviz__ 2740 / 2049 / 507 Регистрация: 17.02.2014 Сообщений: 9,470
	11.07.2019, 08:02
	OlegNN52, из твоего примера, как мне думается, правильный ответ должен быть 2, а не 3. т.к. полные искомые матрицы либо первые символы, первой - второй строки и предпоследние второй - третей, либо первые символы, второй - третьей строки, и также предпоследние второй - третей. приведи код одной из программ, чтобы было ясно о каких матрицах идет речь, пока кажется, что все строковые. 1

@Aviz__ 2740 / 2049 / 507 Регистрация: 17.02.2014 Сообщений: 9,470
	11.07.2019, 15:40
	Не по теме: OlegNN52, Бро, код программ нужно обрамлять тегами JAVA одна из кнопок выше не согласен, что перекрывающиеся считать верно, но хз, ты сам решаешь. 1

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	11.07.2019, 15:43
	OlegNN52, тебя никто не понимает, какие матрицы, что ты считаешь? 1