fork download 
  1. # -*- coding: utf-8 -*-
  2.  
  3.  
  4. class AhoNode:
  5.     ''' Вспомогательный класс для построения дерева
  6.     '''
  7.     def __init__(self):
  8.         self.goto = {}
  9.         self.out = []
  10.         self.fail = None
  11.  
  12.  
  13. def aho_create_forest(patterns):
  14.     '''Создать бор - дерево паттернов
  15.     '''
  16.     root = AhoNode()
  17.  
  18.     for path in patterns:
  19.         node = root
  20.         for symbol in path:
  21.             node = node.goto.setdefault(symbol, AhoNode())
  22.         node.out.append(path)
  23.     return root
  24.  
  25.  
  26. def aho_create_statemachine(patterns):
  27.     '''Создать автомат Ахо-Корасика.
  28.     Фактически создает бор и инициализирует fail-функции
  29.     всех узлов, обходя дерево в ширину.
  30.     '''
  31.     # Создаем бор, инициализируем
  32.     # непосредственных потомков корневого узла
  33.     root = aho_create_forest(patterns)
  34.     queue = []
  35.     for node in root.goto.itervalues():
  36.         queue.append(node)
  37.         node.fail = root
  38.  
  39.     # Инициализируем остальные узлы:
  40.     # 1. Берем очередной узел (важно, что проход в ширину)
  41.     # 2. Находим самую длинную суффиксную ссылку для этой вершины - это и будет fail-функция
  42.     # 3. Если таковой не нашлось - устанавливаем fail-функцию в корневой узел
  43.     while len(queue) > 0:
  44.         rnode = queue.pop(0)
  45.  
  46.         for key, unode in rnode.goto.iteritems():
  47.             queue.append(unode)
  48.             fnode = rnode.fail
  49.             while fnode is not None and key not in fnode.goto:
  50.                 fnode = fnode.fail
  51.             unode.fail = fnode.goto[key] if fnode else root
  52.             unode.out += unode.fail.out
  53.  
  54.     return root
  55.  
  56.  
  57. def aho_find_all(s, root, callback):
  58.     '''Находит все возможные подстроки из набора паттернов в строке.
  59.     '''
  60.     node = root
  61.  
  62.     for i in xrange(len(s)):
  63.         while node is not None and s[i] not in node.goto:
  64.             node = node.fail
  65.         if node is None:
  66.             node = root
  67.             continue
  68.         node = node.goto[s[i]]
  69.         for pattern in node.out:
  70.             callback(i - len(pattern) + 1, pattern)
  71.  
  72.  
  73. ############################
  74. # Демонстрация работы алгоритма
  75. def on_occurence(pos, patterns):
  76.     print "At pos %s found pattern: %s" % (pos, patterns)
  77.  
  78. patterns = ['пизд', 'прошм', 'ебл', 'шмонька', 'хуй', 'сука', 'пидар']
  79. s = "пиздопр0шмондовочкаибливая и сукаХхххуй ебал пидар пидор сYка пNдорас"
  80. root = aho_create_statemachine(patterns)
  81. aho_find_all(s, root, on_occurence)
Success #stdin #stdout 0.01s 7200KB
comments (?)
stdin 
Standard input is empty
stdout 
At pos 0 found pattern: пизд
At pos 55 found pattern: сука
At pos 69 found pattern: хуй
At pos 85 found pattern: пидар
https://ideone.com/ITTVfe
language:
Python (cpython 2.7.16)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!