Сложность «Поисковые слова/строки в матрице символов» Алгоритм

Question

У меня есть задача поиска в сетке букв (20×20 <= MxN <= 1000×1000) слов (5 <= length <= 100) из списка. Любое слово, спрятанное в сетке, всегда имеет форму сегментов зигзага, длина которых может быть всего 2 или 3. Сегменты зигзага могут быть только слева направо или снизу вверх.

Требуемая сложность равна произведению количества букв в сетке и количеству букв из списка.

Для сетки:

•••••••••••••••••••• 
••••••••ate•••••x••• 
•••••••er•••••••e••• 
••••••it••••••••v••• 
••••ell••••••a••f••• 
•••at••••e••••••rbg• 
•••s•••••••ga••••••• 

и список слов {"forward", "iterate", "phone", "satellite"} выход будет

3,6,iterate 
6,3,satellite 

Я сделал это в C++:
Я сохранил все префиксы и слова в unordered_map<string, int> где key префикс/слово и value - 1 для префикса и 2 для слова. Теперь я сделать что-то вроде этого (псевдокод):

for (char c in grid) 
    check(c + ""); 
} 

где:

check(string s) { 
    if s is key in unsorted_map { 
     if (value[s] == 2) //it's a word 
      print s; //and position 
     if (not up 3 time consecutive) //limit the segments <= 3 
      check(s + next_up_char_from_grid); 
     if (not right 3 time consecutive) 
      check(s + next_right_char_from_grid); 
    } 
} 

Эта реализация работает отлично подходит для случайных символов в сетке и слов из словаря, но
сложности C ≃ O (M * N * 2 ^к)> о (М * N * R)
лучшее приближение с ≃ O (M * N * (1,6) ^к) из-за ограничений длины сегментов

M * N = number of chars in grid 
K = the maximum length of any word from list (5 <= K <= 100) 
R = number of chars in list of words 

Худший случай: максимальная сетка, максимальная длина слова и один и тот же одиночный символ в сетке и слово
Как я могу архивировать требуемую сложность? Это возможно только с заданными ограничениями?

Answer 1

Ваша функция check() сделает много повторений.

Для сетки

•aa 
ab• 
aa• 

и слова 'aabaa'

Есть два способа получить 'aabaa', которые являются же после письма 'b'

(сверху, справа, сверху, справа) или (справа, верхняя, верхняя, правая)

С этой целью мы используем массив a[position][n][m] для записи, конкретное слово его префикс длиной position можно получить в сетке [m, n]

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

a[0][2][0] = true 
a[1][1][0] = a[1][2][1] = true 
a[2][1][1] = true 
a[3][0][1] = true 
a[4][0][2] = true 

'aabaa' можно найти в молоть

Так сложность будет N*M*K*S

S - количество слов в списке