собственный алгоритм соответствия строк

Question

Ниже приведен очень известный вопрос в родном сопоставлении строк. Пожалуйста, кто-нибудь может объяснить мне ответ.

Предположим, что все символы в шаблоне P различны. Покажите, как ускорить НАИВ-STRING Сличитель бежать во времени O (N) на текст Т. н-символьного

Answer 1

Основная идея:

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

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

Вот некоторые псевдо-код, который не должен быть слишком трудно понять:

input[n] 
pattern[k] 
pPos = 0 
iPos = 0 
while iPos < n 
    if pPos == k 
    FOUND! 
    if pattern[pPos] == input[iPos] 
    pPos++ 
    iPos++ 
    else 
    // if pPos is already 0, we need to increase iPos, 
    // otherwise we just keep comparing the same characters 
    if pPos == 0 
     iPos++ 
    pPos = 0 

Легко видеть, что iPos увеличивается по крайней мере, каждый второй цикл, таким образом, может быть в большинстве 2n прогонов цикла, что делает время работы O(n).

Answer 2

Когда T [i] и P [j] не совпадают с NAIVE-STRING-MATCHER, мы можем пропустить все символы перед T [i] и начать новое соответствие с T [i + 1] с P [1].

НАИВНЫЙ-СТРОКА-согласовани (Т, Р)

1 п Длина [Т]

2 м Длина [Р]

3 для S 0 до п - м

4, если P [1. , m] = T [s + 1. , s + т]

5 затем распечатать «Узор происходит со сдвигом» s

Answer 3

наивные реализации алгоритма Строка поиска в Python 2.7: https://gist.github.com/heyhuyen/4341692

В середине реализации алгоритма поиска строки Бойер-Мура, я решил поиграть с моим оригинальным алгоритмом наивного поиска. Он реализован как метод экземпляра, который берет строку для поиска. Объект имеет атрибут «шаблон», который соответствует шаблону.

1) Вот исходная версия метода поиска с использованием двойного цикла for. Делает звонки в диапазоне и Len

def search(self, string): 
    for i in range(len(string)): 
     for j in range(len(self.pattern)): 
      if string[i+j] != self.pattern[j]: 
       break 
      elif j == len(self.pattern) - 1: 
       return i 
    return -1 

2) Вот вторая версия, с использованием двойного While-цикл вместо этого. Чуть быстрее, не делая звонки в диапазоне

def search(self, string): 
    i = 0 
    while i < len(string): 
     j = 0 
     while j < len(self.pattern) and self.pattern[j] == string[i+j]: 
      j += 1 
     if j == len(self.pattern): 
      return i 
     i += 1 
    return -1 

3) Вот оригинал, замена диапазон с xrange. Быстрее, чем оба предыдущих.

def search(self, string): 
    for i in xrange(len(string)): 
     for j in xrange(len(self.pattern)): 
      if string[i+j] != self.pattern[j]: 
       break 
      elif j == len(self.pattern) - 1: 
       return i 
    return -1 

4) Сохранение значений в локальных переменных = выигрыш! С циклом double while это самый быстрый.

def search(self, string): 
    len_pat = len(self.pattern) 
    len_str = len(string) 
    i = 0 
    while i < len_str: 
     j = 0 
     while j < len_pat and self.pattern[j] == string[i+j]: 
      j += 1 
     if j == len_pat: 
      return i 
     i += 1 
    return -1