Алгоритм прямого поиска подстроки в строке 

Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь

КАТЕГОРИИ:

Археология
Биология
Генетика
География
Информатика
История
Логика
Маркетинг
Математика
Менеджмент
Механика
Педагогика
Религия
Социология
Технологии
Физика
Философия
Финансы
Химия
Экология

ТОП 10 на сайте

Приготовление дезинфицирующих растворов различной концентрации

Техника нижней прямой подачи мяча.

Франко-прусская война (причины и последствия)

Организация работы процедурного кабинета

Смысловое и механическое запоминание, их место и роль в усвоении знаний

Коммуникативные барьеры и пути их преодоления

Обработка изделий медицинского назначения многократного применения

Образцы текста публицистического стиля

Четыре типа изменения баланса

Задачи с ответами для Всероссийской олимпиады по праву


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Влияние общества на человека

Приготовление дезинфицирующих растворов различной концентрации

Практические работы по географии для 6 класса

Организация работы процедурного кабинета

Изменения в неживой природе осенью

Уборка процедурного кабинета

Сольфеджио. Все правила по сольфеджио

Балочные системы. Определение реакций опор и моментов защемления

Алгоритм прямого поиска подстроки в строке

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒


1. Установить i на начало строки S, т.е. i = 0.

2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм завершен (вхождения нет).

3. Начиная с i -го символа s провести посимвольное сравнение строк S и p, т. е. S [i] и P [0], S [i+1] и P [1],…, S [ i + M – 1] и P [ M – 1].

4. Если хотя бы одна пара символов не совпала, то увеличить i и повторить шаг 2, иначе алгоритм завершен (вхождение найдено).

 

Приведем пример, иллюстрирующий этот процесс. Символы образца, подвергшиеся сравнению, выделены синим цветом. Здесь

S: на дворе трава, на траве дрова;

P: траве.

 

н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
т р а в е                                                  
  т р а в е                                                
    т р а в е                                              
      т р а в е                                            
        т р а в е                                          
          т р а в е                                        
            т р а в е                                      
              т р а в е                                    
                т р а в е                                  
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                  т р а в е                                
                    т р а в е                              
                      т р а в е                            
                        т р а в е                          
                          т р а в е                        
                            т р а в е                      
                              т р а в е                    
                                т р а в е                  
                                  т р а в е                
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              
                                    т р а в е              

 

Приведем две блок-схемы, описывающие алгоритм. В первой блок-схеме используется дополнительная переменная flag, которая явно изменяет свое значение с 0 на 1 при обнаружении вхождения образца P в текст S.

 

 

 

Во второй блок-схеме используется тот факт, что при j = M мы дошли до конца образца P, тем самым обнаружив его вхождение в строку S.

 

 

Алгоритм работает достаточно эффективно, если при сравнении образца P с фрагментом текста S довольно быстро выявляется несовпадение (после нескольких сравнений во внутреннем цикле). Это случается довольно часто, но в худшем случае (когда в строке часто встречаются фрагменты, во многих символах совпадающие с образцом) производительность алгоритма значительно падает. Приведем пример. Здесь

S: учиться, учить, учитель

P: учитель

 

у ч и т ь ,   у ч и т ь с я ,   у ч и т е л ь
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
у ч и т е л ь                                
  у ч и т е л ь                              
    у ч и т е л ь                            
      у ч и т е л ь                          
        у ч и т е л ь                        
          у ч и т е л ь                      
            у ч и т е л ь                    
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
              у ч и т е л ь                  
                у ч и т е л ь                
                  у ч и т е л ь              
                    у ч и т е л ь            
                      у ч и т е л ь          
                        у ч и т е л ь        
                          у ч и т е л ь      
                            у ч и т е л ь    
                              у ч и т е л ь  
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь
                                у ч и т е л ь

 

1.2.2. Алгоритм Боуера и Мура

 

Рассмотрим самый «плохой» для линейного поиска случай:

Подсчитаем для него число сравнений. Так как несовпадение символов происходит на последней букве образца, в каждом внешнем цикле производится сравнений. Так как образец находится в конце строки, число внешних циклов равно , то есть общее число сравнений есть . В 1975 году Р. Боуер и Д. Мур предложили алгоритм, который значительно укоряет обработку данного случая. Алгоритм носит название БМ-поиска.

В отличие от линейного поиска, сравнение в БМ-поиске начинается не с начала, а с конца образца . Кроме того, образец предварительно анализируется, и благодаря этому образец сдвигается не на один символ, а в общем случае на несколько. Рассмотрим механизм сдвига на примере.

на дворе трава, на траве дрова

дрова

Начинаем сравнение с последнего символа образца. Символы, подвергшиеся сравнению, выделены: в строке – красным цветом, в образце – синим. Индекс указывает на первый сравниваемый символ в строке (первоначально ), индексы и – на сравниваемые символы в образце и строке соответственно. Сначала , , затем и уменьшаются на единицу, пока не произойдет несовпадение символов и , либо не закончится образец ().

 

        k                                                  
        j                                                  
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
д р о в а                                                  
        i                                                  

 

Совпадения не произошло при первом же сравнении, необходимо сдвинуть образец, то есть увеличить индекс . В БМ-поиске образец сдвигается так, чтобы «под» символом (в таблице) оказался совпадающий с ним ближайший к концу символ образца (иначе при совпадения и точно не произойдет). Значит, в данном случае сдвигаем образец на одну позицию вправо, то есть увеличиваем индекс на единицу.

 

          k                                                
          j                                                
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
  д р о в а                                                
          i                                                

 

Совпадения образца со строкой опять не произошло, сдвигаем образец. Теперь и расстояние от конца образца до символа в нем равно двум, значит, индекс увеличиваем на два.

 

              k                                            
              j                                            
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
      д р о в а                                            
              i                                            

 

И опять не произошло совпадения образца со строкой. Теперь , такого символа в образце нет, поэтому мы можем сдвинуть образец сразу на его длину, то есть увеличить индекс на .

 

                        k                                  
                        j                                  
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                д р о в а                                  
                        i                                  

 

Здесь , расстояние от конца образца до символа равно единице, значит, индекс увеличиваем на единицу.

 

                          k                                
                      j                                    
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                  д р о в а                                
                      i                                    

 

Теперь , такой символ в образце есть, но лишь в последней позиции, в остальной части образца его нет, поэтому увеличиваем индекс на длину образца .

 

                                    k                      
                                    j                      
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                            д р о в а                      
                                    i                      

 

Символа в образце нет, увеличиваем индекс на .

 

                                              k            
                                              j            
н а   д в о р е   т р а в а ,   н а   т р а в е   д р о в а
                                      д р о в а            
                                              i            

 

Символа в образце нет, увеличиваем индекс на .

 


⇐ Предыдущая123456Следующая ⇒

Поделиться:


Читайте также:


Алгоритмические операторы Matlab
Конструирование и порядок расчёта дорожной одежды
Исследования учёных: почему помогают молитвы?
Почему терпят неудачу многие предприниматели?


Последнее изменение этой страницы: 2017-02-08; просмотров: 1677; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.218.129.100 (0.046 с.)