Строка матч в скользящем окне

Question

Допустим, у вас есть файл, который имеет следующую строку

a a a b a a b a a b b a b 

У вас нет доступа к файлу, но функция FetchNextChar(), что дает по одному символу за раз.

и шаблон для сопоставления a a b

Как бы вы подсчитывают общее число обращений?

Вот что я думаю.

1. Если символ неправдоподобное это первый символ шаблона («а»), а затем добавить его в очередь
2. Начало добавления/создать связанный список для следующего полукокса, если он совпадает со следующим полукоксом шаблона

Таким образом, после 1-го выборки мы

Pattern -a 
Queue - a 

Then 

Pattern -a a 
Queue[0] a->a 
Queue[1] a 


3rd 
Pattern a a b 
Queue[0] a -->a--> a //doesn't match, dequeue 
Queue[1]  a-> a 
Queue[2]    a 

Я думаю, что это будет работать, но этот вопрос я вижу, если есть кратна Чара, что матч с первым символом шаблона я бы сохранить, добавив к очереди и, следовательно, продолжать увеличивать список.

Любые мысли?

Answer 1

Это может быть эффективно решена с помощью Rabin–Karp algorithm вычисления rolling hash для скользящего окна, наивный функция качению хэш просуммировать ASCII код символов, но вы можете использовать этот массив primes сделать столкновения менее, я проверил эти простые числа и дал мне несколько столкновений на большое и, так струнное и сопоставлении с образцом:

primes[] = {13 , 7963 , 17443 , 27527 , 37879 , 48673 , 59407 , 70729 , 81883 , 93251 , 104789 , 116531 , 128239 , 139969 , 151783 , 163883 , 176159 , 188029 , 200257 , 212447 , 224831 , 237283 , 249517 , 262217 , 274661 , 287173}; 

И вот псевдокод для вышеуказанного алгоритма для печати количества совпадений:

stream = "aaabaabaabbab"; 
pattern = "aab"; 
queue window; 

patternHash = 0; 
for ch in pattern: 
    patternHash = patternHash + primes[ch - 'a'] 

first = readFromStream(stream) 
window.enqueue(first) 
windowHash = primes[first - 'a'] 
for i = 0 to pattern.size(): 
    ch = readFromStream(stream) 
    window.enqueue(ch) 
    windowHash = windowHash + primes[ch - 'a'] 

count = 0 
for i = pattern.size() to stream.size(): 
    if windowHash == patternHash 
     if window == pattern 
      count = count + 1 
    ch = readFromStream(stream) 
    window.enqueue(ch) 
    windowHash = windowHash - primes[window.first() - 'a'] 
    windowHash = windowHash + primes[ch - 'a'] 
    window.dequeue() 

print count 

Answer 2

Вы могли бы использовать алгоритм состояния на основе:

Мы можем видеть, что каждый раз, когда 'b' читается мы идем на state=0 и число появления рисунка увеличивается на единицу, если мы были на state=2. Когда считывается 'a', мы переходим к следующему состоянию, ограниченному state=2.

здесь скрипт Python, который реализует алгоритм

stream = ['a','a','a','b','a','a','b','a','a','b','b','a','b'] 

state = 0 
nbMatch = 0 

for c in stream: 
    if c=='a': 
     if state==0 or state==1: 
      state = state+1 
     #if state == 2: state=2 
    else: #c=='b' 
     if state==2: 
      nbMatch = nbMatch+1 
     state = 0 
    print c, " state=", state 
print nbMatch