Độ phức tạp của cụm từ "Tìm kiếm từ/chuỗi trong ma trận Char" Thuật toán

Question

Tôi có nhiệm vụ tìm kiếm trong một mạng lưới các từ (20×20 <= MxN <= 1000×1000) từ (5 <= length <= 100) từ danh sách. Bất kỳ từ nào ẩn trong lưới luôn luôn ở dạng một phân đoạn zig-zag có chiều dài chỉ có thể là 2 hoặc 3. Phân đoạn Zigzag chỉ có thể từ trái sang phải hoặc từ dưới lên trên.

Độ phức tạp được yêu cầu bằng sản phẩm của số lượng chữ cái trong lưới và số lượng chữ cái trong danh sách.

Đối với lưới điện:

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

và danh sách các từ {"forward", "iterate", "phone", "satellite"} đầu ra sẽ

3,6,iterate 
6,3,satellite 

Tôi đã làm điều này trong C++:
tôi đã lưu tất cả các tiền tố và lời nói trong một unordered_map<string, int> nơi key là tiền tố/từ và value là 1 cho tiền tố và 2 cho từ. Bây giờ tôi làm điều gì đó như thế này (giả):

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

nơi:

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); 
    } 
} 

thi này hoạt động tuyệt vời cho chars ngẫu nhiên trong lưới và lời nói từ điển nhưng
phức tạp C ≃ O (M * N * 2 ^K)> O (M * N * R)
Một xấp xỉ tốt hơn C ≃ O (M * N * (1,6) ^K) vì những hạn chế của phân đoạn dài

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 

Trường hợp xấu nhất: lưới tối đa, độ dài từ tối đa và cùng một char trong lưới và từ
Làm cách nào để lưu trữ độ phức tạp cần thiết? Có thể chỉ với các hạn chế nhất định?

Answer 1

Chức năng check() của bạn sẽ thực hiện nhiều thao tác lặp lại.

Đối với lưới

•aa 
ab• 
aa• 

và từ 'aabaa'

Có hai cách để có được 'aabaa' mà là cùng sau khi lá thư 'b'

(top, right, top, right) hoặc (bên phải, trên cùng, trên cùng, bên phải)

Từ đặc điểm này, chúng tôi sử dụng mảng a[position][n][m] để ghi lại liệu một từ cụ thể tiền tố của nó với chiều dài position có thể được nhận vào lưới [m, n]

Đối với ví dụ trước, làm theo trình tự như vậy

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' có thể được tìm thấy trong xay

Vì vậy, độ phức tạp sẽ N*M*K*S

S là số từ trong danh sách