Python cho người Việt

Python cho người Việt

Phỏng vấn: Cộng chuỗi ít tốn nhất

written by Nguyễn Thành Nam, on Mar 23, 2015 2:08:53 AM.

Câu hỏi

Cho n chuỗi, tìm cách cộng các chuỗi này lại theo một thứ tự nào đó sao cho ít tốn bộ nhớ nhất.

Ví dụ: Cho chuỗi A="abc", B=wxyz, C=g, và xét hai cách cộng chuỗi sau:

  1. Cộng AB trước, sau đó cộng với C. A + B sẽ tốn 3 + 4 = 7. Sau đó cộng thêm C sẽ tốn 7 + 1 = 8. Tổng cộng tốn 7 + 8 = 15.
  2. Cộng AC trước, sau đó cộng với B. A + C tốn 3 + 1 = 4. Sau đó cộng thêm B sẽ tốn 4 + 4 = 8. Tổng cộng tốn 4 + 8 = 12.

Cách cộng chuỗi thứ 2 đỡ tốn bộ nhớ hơn cách thứ 1, và cũng là cách tốn ít bộ nhớ nhất.

Phân tích

Việc cộng n chuỗi với nhau luôn luôn tốn n-1 phép cộng chuỗi, và tạo ra chuỗi cuối cùng với độ lớn không đổi. Do đó, lý do tốn bộ nhớ không phải là vì kết quả cuối cùng, mà là do các mảng nhớ tạm ta phải sử dụng để chứa kết quả của các phép cộng chuỗi này.

Xét ba chuỗi bất kỳ với độ lớn x <= y <= z. Ta cần thực hiện 2 phép cộng chuỗi, và độ lớn của chuỗi cuối cùng sẽ là tổng của x + y + z không đổi. Độ lớn của chuỗi tạm sẽ là tổng này trừ đi độ lớn của chuỗi gốc trong phép cộng chuỗi thứ 2. Dễ thấy rằng nếu ta để dành chuỗi có độ lớn z để cộng cuối cùng, thì độ lớn của chuỗi tạm sẽ là nhỏ nhất, x + y.

Do đó, ta sẽ để dành chuỗi có chiều dài lớn nhất cho các phép cộng sau cùng, chuỗi có độ dài lớn thứ hai cho phép cộng kế cuối... Vì vậy, cách giải bài toán này chỉ đơn giản là sắp xếp các chuỗi đã cho theo thứ tự tăng dần về độ lớn chuỗi.

Phần cài đặt xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi phù hợp để trao đổi thêm về những vấn đề tương tự.

Phỏng vấn: In ra phần tử nhỏ thứ n trong cây nhị phân

written by Nguyễn Thành Nam, on Mar 19, 2015 11:19:23 AM.

Câu hỏi

Cho một cây nhị phân tìm kiếm (binary search tree), in ra phần tử nhỏ thứ n trong cây này.

Ví dụ: Với cây nhị phân như sau:

                7
           5         9
        3     6         10

Phần tử nhỏ nhất (n=1) là 3, phần tử nhỏ thứ 2 là 6, phần tử nhỏ thứ 3 là 5.

Phân tích

Vì đây là cây nhị phân tìm kiếm nên ta luôn có điều kiện bất biến là các đỉnh bên trái luôn luôn nhỏ hơn hoặc bằng, và các đỉnh bên phải luôn luôn lớn hơn hoặc bằng giá trị của đỉnh đang xét.

Do đó, phần tử nhỏ nhất thứ n cũng là phần tử thứ n trong quá trình duyệt cây theo thứ tự trái, giữa, phải, tức là theo cách tìm kiếm ưu tiên chiều sâu (depth first search).

# encoding: utf-8
def solve(root, n):

    def traverse(node, nr_seen):
        '''Trả về (số đỉnh đã qua, và kết quả).'''
        if node is None:
            return nr_seen, None

        # Tìm trong nhánh trái
        nr_seen, answer = traverse(node.left, nr_seen)
        if answer is not None:
            # Tìm thấy kết quả bên nhánh trái.
            return nr_seen, answer

        nr_seen += 1
        if nr_seen == n:
            # Đỉnh hiện tại chính là đỉnh cần tìm.
            return nr_seen, node.value

        # Tìm trong nhánh phải
        nr_seen, answer = traverse(node.right, nr_seen)
        return nr_seen, answer

    nr_seen, answer = traverse(root, 0)
    return answer


class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


root = Node(7, Node(5, Node(3), Node(6)), Node(9, None, Node(10)))
assert(solve(root, 1) == 3)
assert(solve(root, 2) == 5)
assert(solve(root, 3) == 6)
assert(solve(root, 4) == 7)
assert(solve(root, 5) == 9)
assert(solve(root, 6) == 10)

Phỏng vấn: Tìm các từ cùng bộ ký tự

written by Nguyễn Thành Nam, on Mar 16, 2015 9:05:00 AM.

Câu hỏi

Cho một quyển từ điển D, và một từ W trong từ điển, yêu cầu xuất ra tất cả các từ có trong từ điển với cùng bộ ký tự như từ W.

Ví dụ từ mary có bộ ký tự là một chữ m, một chữ a, một chữ r và một chữ y, từ army cũng có cùng bộ ký tự như vậy.

Phân tích

Mối quan hệ giữa từ, và bộ ký tự là 1-n, tức là một từ sẽ có một bộ ký tự, nhưng một bộ ký tự có thể có nhiều từ. Do đó, cách giải bài này là thể hiện mối quan hệ giữa từ và bộ ký tự của nó.

Với mỗi từ X trong từ điển, ta sẽ tìm ra bộ ký tự K tương ứng của từ đó, và lưu X vào danh sách các từ có bộ ký tự K. Để trả lời câu hỏi, ta chỉ việc in ra danh sách các từ có bộ ký tự tương ứng với W.

Độ phức tạp thực thi của cách giải này là O(1) với O(n) bước xử lý trước (preprocessing), và tốn O(n) bộ nhớ.

from collections import defaultdict

def get_alphabet(word):
    count = defaultdict(int)
    for c in word:
        count[c] += 1
    # vì kiểu dict là khả biến, nên ta phải
    # chuyển "count" thành kiểu string để
    # có thể dùng làm khóa trong một dict khác
    r = []
    for k in sorted(count.keys()):
        r.append('%c%d' % (k, count[k]))
    return ''.join(r)

assert(get_alphabet('aaabb') == 'a3b2')

def solve(D, W):
    alpha_to_words = defaultdict(list)
    for word in D:
        alpha = get_alphabet(word)
        alpha_to_words[alpha].append(word)
    return alpha_to_words[get_alphabet(W)]

assert(solve(['mary', 'army', 'vithon'], 'mary') == ['mary', 'army'])

Cách giải trên sẽ áp dụng tốt nếu ta cần trả lời cho một loạt các từ W bởi vì ta chỉ tốn thời gian xử lý trước một lần, và sau đó có thể truy vấn alpha_to_words cho mỗi từ W sau đó. Tuy nhiên, nếu ta chỉ cần trả lời câu hỏi cho duy nhất một từ W thì việc tốn thêm O(n) bộ nhớ cho alpha_to_words là không cần thiết. Trong trường hợp đó, ta chỉ việc xét từng từ trong D, nếu nó có cùng bộ ký tự như W thì ta xuất nó ra ngay.

Phỏng vấn: Số lượng số chính phương ít nhất để có tổng là n

written by Nguyễn Thành Nam, on Mar 14, 2015 10:53:00 PM.

Câu hỏi

Cho một số nguyên dương n, tìm số lượng số chính phương ít nhất có tổng là n.

Ví dụ: Với n là 9, thì đáp án là 1 (vì 9 là số chính phương), với n là 10 thì đáp án là 2 (9 + 1), với n là 11, đáp án là 3 (9 + 1 + 1), với n là 12 thì đáp án là 3 (4 + 4 + 4).

Phân tích

Giả sử như ta đã có đáp án cho tất cả các giá trị từ 1 đến n-1, đáp án cho n sẽ là min(1 + đáp án của (n-x)) với x là một số chính phương. Nói một cách khác, với mỗi số chính phương x nhỏ hơn hoặc bằng n, số lượng số chính phương cần để có tổng là n sẽ là số lượng số chính phương cần để tạo ra tổng là n-x thêm 1 (chính là x). Do đó, đáp án cho n sẽ chính là min của các cách tạo ra tổng n từ các số chính phương nhỏ hơn hoặc bằng n.

Như vậy, ta có thể giải bài toán này bằng cách điền vào bảng trả lời (đặt tên là ans) cho các giá trị từ 0 đến n. Kết quả cuối cùng sẽ là giá trị của ans[n].

Cách giải các bài toán mà đáp án cho giá trị cuối cùng có thể được tính từ đáp án của các giá trị trước, và ta có thể tính các giá trị này bằng cách từ từ điền vào bảng, được gọi là quy hoạch động (dynamic programming).

def solve(n):
    ans = [n] * (n + 1)
    ans[0] = 0
    ans[1] = 1
    for i in xrange(2, n + 1):
        x = 0
        while True:
            x += 1
            x2 = x * x
            if x2 > i:
                break
            ans[i] = min(ans[i], 1 + ans[i - x2])
    return ans[n]

assert(solve(9) == 1)
assert(solve(10) == 2)
assert(solve(11) == 3)
assert(solve(12) == 3)

Độ phức tạp thực thi của cách giải này là O(n * sqrt(n)), và tốn O(n) bộ nhớ.

Phỏng vấn: Cài đặt "ngăn xếp" với thao tác "min/max"

written by Nguyễn Thành Nam, on Mar 11, 2015 10:07:20 AM.

Câu hỏi

Cài đặt cấu trúc dữ liệu ngăn xếp với thao tác trả về phần tử nhỏ (hay lớn) nhất hiện tại của ngăn xếp.

Phân tích

Ngăn xếp (stack) là cấu trúc dữ liệu vào sau ra trước (Last In, First Out). Nói đến ngăn xếp ta phải nhớ ngay đến hai tác vụ quan trọng nhất là đẩy vào (push) và lấy ra (pop). Khi push dữ liệu vào, dữ liệu sẽ nằm trên cùng của ngăn xếp (top of stack). Khi pop, dữ liệu trên cùng của ngăn xếp sẽ được lấy ra khỏi ngăn xếp.

Ngoài hai tác vụ trên, ta còn có thể kể thêm một số tác vụ truy vấn cấu trúc dữ liệu này ví dụ như số lượng dữ liệu có trong ngăn xếp, liệu ngăn xếp có dữ liệu hay không, hay xem dữ liệu trên cùng của ngăn xếp (mà không lấy nó ra khỏi ngăn xếp).

Câu hỏi này yêu cầu ta cài đặt hai tác vụ push, pop, và thêm tác vụ min (hoặc max) để cho biết dữ liệu nhỏ nhất (hay lớn nhất) hiện tại trong ngăn xếp mà không lấy nó ra.

Cách giải dễ nhất

Điều đầu tiên ta nghĩ đến sẽ là tạo một biến để chứa giá trị cực tiểu (hay cực đại). Khi push vào, ta sẽ cập nhật lại biến này nếu cần. Khi hỏi min thì ta chỉ cần trả về giá trị này.

Vấn đề phức tạp là khi pop ra, làm sao để ta cập nhật lại biến cực tiểu đó? Một cách rất đơn giản là ta sẽ duyệt lại toàn bộ các dữ liệu đang có trong ngăn xếp để đưa ra giá trị cực tiểu mới.

Cách giải này dẫn đến độ phức tạp O(1) cho push, O(1) cho minO(n) cho pop.

class Stack(object):

    def __init__(self):
        self.store = []
        self.min = None

    def push(self, value):
        self.store.append(value)
        if self.min is None or self.min < value:
            self.min = value

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        if not self.store:
            self.min = None
        else:
            self.min = min(self.store)
        return r

    def min(self):
        return self.min

Cách giải O(1) cho pop

Ta nhận thấy rằng tác vụ pop có độ phức tạp O(n) là bởi vì ta phải duyệt lại toàn bộ các phần tử hiện tại của ngăn xếp để xác định phần tử cực tiểu.

Một phương pháp thường được sử dụng để tăng tốc tác vụ là sử dụng bộ nhớ tạm (cache). Ta sẽ tráo đổi giữa thời gian chạy, và không gian nhớ. Nếu như ở mỗi lần push, ta lưu giá trị cực tiểu của các phần tử trong ngăn xếp này vào trong một ngăn xếp thứ hai, thì khi trả lời min, ta chỉ việc nhìn vào (peek) ngăn xếp thứ hai là sẽ có ngay kết quả. Và khi pop thì ta chỉ việc pop ở cả hai ngăn xếp. Các tác vụ này đều có độ phức tạp O(1), nhưng ta sẽ tốn thêm O(n) bộ nhớ cho ngăn xếp thứ hai.

class StackBase(object):

    def __init__(self):
        self.store = []

    def push(self, value):
        self.store.append(value)

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        return r

    def peek(self):
        return self.store[-1]

    def __bool__(self):
        return bool(self.store)


class StackWithMin(object):

    def __init__(self):
        self.store = StackBase()
        self.mins = StackBase()

    def push(self, value):
        self.store.push(value)
        if not self.mins or self.mins.peek() < value:
            self.mins.push(value)
        else:
            self.mins.push(self.min.peek())

    def pop(self):
        self.mins.pop()
        return self.store.pop()

    def min(self):
        return self.mins.peek()

Cách giải O(1) cho pop cải tiến

Cách giải trên tráo đổi O(1) bộ nhớ và O(n) thời gian cho O(n) bộ nhớ và O(1) thời gian.

Vấn đề dẫn đến O(n) bộ nhớ là do ở mỗi lần push ta cũng lưu lại giá trị cực tiểu của các phần tử hiện tại. Nếu như ta chỉ lưu vị trí của phần tử cực tiểu, thì ta sẽ tiết kiệm được bộ nhớ một chút. Ta chỉ cần lưu lại vị trí của phần tử cực tiểu mới, nếu vị trí này khác với vị trí hiện tại. Khi pop ra, nếu số lượng phần tử hiện tại ít hơn vị trí của phần tử cực tiểu thì ta cũng pop luôn vị trí này ra khỏi ngăn xếp thứ hai. Điều này đảm bảo điều kiện bất biến vị trí của phần tử cực tiểu luôn luôn nhỏ hơn số lượng phần tử trong ngăn xếp.

Cài đặt này xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi tốt nhất để bạn đọc trao đổi thêm.

Phỏng vấn: Tìm tích của mọi phần tử trừ phần tử hiện tại

written by Nguyễn Thành Nam, on Mar 8, 2015 2:05:00 PM.

Câu hỏi

Cho một danh sách các số thực A, trả về một danh sách trong đó phần tử tại vị trí i có giá trị là tích của các phần tử không phải ở vị trí i trong danh sách A.

Phân tích

Trường hợp ngoại lệ

Nếu A chỉ có một phần tử thì giá trị trả về sẽ là gì? Người đi phỏng vấn phải hỏi ngược lại được người phỏng vấn trường hợp này.

Cách giải đơn giản

Cách giải đơn giản nhất là ta thực hiện hai vòng lặp để tính giá trị của từng phần tử của danh sách B.

def solve(A):
  B = [1] * len(A)
  for i in xrange(len(A)):
    for j in xrange(len(A)):
      if i != j:
        B[i] *= A[j]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải này có độ phức tạp là O(n^2).

Cách giải O(n)

Có hai nhận xét đơn giản sau:

  1. Nếu như trong số phần tử còn lại có giá trị 0, thì tích số cũng sẽ là 0.
  2. Giá trị của B[i] sẽ là tích của toàn bộ các phần tử trong A, chia cho A[i]. Ta có thể tính tích của toàn bộ các phần tử trong A qua một vòng lặp, và dùng một vòng lặp khác để tính từng giá trị của B.
def solve(A):
  nr_zeros = 0
  product = 1
  for i in xrange(len(A)):
    if A[i] == 0:
      nr_zeros += 1
    else:
      product *= A[i]
  if nr_zeros >= 2:
    return [0] * len(A)
  B = [0] * len(A)
  for i in xrange(len(B)):
    if A[i] == 0:
      B[i] = product
    elif nr_zeros != 1:
      B[i] = product / A[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải không dùng phép chia

Ta nhận thấy rằng B[i] là tích của các phần tử từ 0 đến i-1 và từ i+1 đến n của A (với n là số phần tử trong A). Nói một cách khác, giá trị trong Btích của hai phần liên tục từ bên trái, và từ bên phải của A . Do đó, ta sẽ sử dụng hai danh sách tạm left_productright_product để chứa tích các phần tử trong A từ bên trái, và từ bên phải, loại trừ phần tử đang xét.

def solve(A):
  left_product = [1] * len(A)
  right_product = [1] * len(A)
  for i in xrange(1, len(A)):
    left_product[i] = left_product[i - 1] * A[i - 1]
  for i in xrange(len(A) - 2, -1, -1):
    right_product[i] = right_product[i + 1] * A[i + 1]
  B = [1] * len(A)
  for i in xrange(len(A)):
    B[i] = left_product[i] * right_product[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Khi đọc kỹ đoạn mã trên, ta sẽ thấy rằng có lẽ danh sách left_product là thừa. Thay vào đó, trong quá trình tính B, ta có thể giữ một biến tạm cho biết tích từ A[0] đến A[i - 1]. Phần này xin được dành làm một thử thách nhỏ cho bạn đọc. Nếu bạn giải ra, xin hãy cùng trao đổi trong diễn đàn.

Phỏng vấn: Cách mua và bán lời nhất

written by Nguyễn Thành Nam, on Mar 6, 2015 11:47:00 AM.

Câu hỏi

Giả sử như bạn có thông tin về giá của một món hàng trong một khoảng thời gian nào đó. Tìm ngày bạn sẽ mua, và ngày bạn sẽ bán món hàng đó để đạt được lợi nhuận cao nhất.

Đầu vào: một danh sách các giá trị thực là giá của món hàng từng ngày.

Đầu ra: hai chỉ mục trong danh sách là ngày mua, và ngày bán.

Ví dụ: với dữ liệu vào [10, 13, 9, 10, 11], thì kết quả là (0, 1) ý là mua ngày 0 với mức giá 10, bán ra ngày 1 với mức giá 13, lợi nhuận cao nhất là 3 đơn vị.

Phân tích

Gọi danh sách đầu vào là A. Câu hỏi này yêu cầu chúng ta tìm hai chỉ mục xy trong A sao cho A[y] - A[x] lớn nhất, với điều kiện x < y.

Đặt min_x là chỉ mục của giá thấp nhất trong danh sách A. Khi xét đến phần tử i trong danh sách A, ta sẽ gặp một số trường hợp sau:

  1. Giá giảm: A[i] < A[min_x] Đây là cơ hội mua vào nên ta sẽ đặt min_x = i.
  2. Giá tăng: A[i] >= A[min_x] Đây là cơ hội bán ra nên ta sẽ phải xét thêm A[i] - A[min_x] > A[y] - A[x], tức là bán vào lúc này có lời hơn lúc trước không. Nếu có, ta sẽ cập nhật y, x = i, min_x.

Cài đặt

def solve(A):
  x = y = min_x = 0
  for i in xrange(1, len(A)):
    if A[i] < A[min_x]:
      min_x = i
    elif A[i] - A[min_x] >= A[y] - A[x]:
      x, y = min_x, i
  return (x, y)

assert(solve([10, 13, 9, 10, 11]) == (0, 1))

Danh sách nhảy cóc (Skip List)

written by Phan Đắc Anh Huy, on May 1, 2014 10:01:00 PM.

Giới thiệu

Qua các lượt bài trước, chúng ta đã thảo luận về thuận toán tìm kiếm nhị phân và ngăn (partition). Cả hai thuận toán này đều dựa trên cấu trúc dữ liệu mảng (array) vốn rất quen thuộc với chúng ta.

Ngoài ra, hai thuật toán trên được xếp vào nhóm thuật toán tất định (determistic algorithm). Các thuật toán thuộc nhóm này thỏa mãn hai điều kiện:

  • Luôn trả về kết quả giống nhau nếu được cung cấp cùng một dữ liệu đầu vào.

  • Các trạng thái (state) trong quá trình tính toán phải giống nhau với cùng một dữ liệu đầu vào.

Trong bài viết này tác giả đề cập đến cấu trúc dữ liệu "Danh Sách Nhảy Cóc" (Skip List), cơ chế hoạt động của cấu trúc dữ liệu này (bao gồm các thao tác Thêm, Xóa, Tìm Kiếm) phụ thuộc vào yếu tố ngẫu nhiên vì vậy nó được xếp vào nhóm thuật toán ngẫu tính (randomized algorithm), trái ngược với nhóm thuật toán tất định.

Mục đích

Một cấu trúc dữ liệu đơn giản nhưng hiệu quả trên các tác vụ cơ bản: Thêm, Xóa và Tìm Kiếm.

Định nghĩa

Danh sách nhảy cóc S là một tập hợp các danh sách S[0], S[1] ... S[N-1]. Để dễ hình dung chúng ta xem mỗi danh sách con tương ứng với một "tầng", trong đó 0 là tầng thấp nhất, cho đến N-1 là tầng cao nhất. Danh sách nhảy cóc luôn thỏa mãn các điều kiện:

  • Mỗi danh sách con chứa các giá trị theo thứ tự tăng dần.

  • Phần từ đầu và cuối mỗi danh sách con đều là NULL.

  • Danh sách ở tầng cao hơn là dãy con của danh sách tầng dưới.

Ví dụ một trạng thái của danh sách nhảy cóc chứa dãy số 12, 23, 34, 46, 64, 78, 89

S[3]    NULL             23                                              NULL
S[2]    NULL             23                      64                      NULL
S[1]    NULL             23      34              64      78              NULL 
S[0]    NULL     12      23      34      46      64      78      80      NULL

Tìm kiếm trong danh sách

Gọi K là giá trị cần tìm kiếm. Ý tưởng chính của thuật toán là cố gắng duyệt càng xa càng tốt trên tầng cao hơn và tiếp tục ở tầng thấp hơn cho đến khi không thể duyệt được nữa.

Thuật toán bắt đầu từ phần tử đầu tiên, tầng trên cùng của danh sách. Duyệt theo quy luật:

  • Nhảy sang phần tử kế tiếp trên cùng tầng nếu phần tử tiếp theo đó khác NULL và bé hơn hoặc bằng K.

  • Nếu không thể di chuyển trên cùng tầng được nữa:

    • Dừng duyệt nếu như đang ở tầng thấp nhất.

    • Ngược lại, nhảy xuống phần tử ngay bên dưới ở tầng tiếp theo.

Sau khi kết thúc duyệt danh sách, nếu phần tử hiện tại bằng K, thuật toán kết luận tìm được K, ngược lại K không tồn tại trong danh sách.

Ví dụ dưới đây minh họa việc tìm kiếm K = 85 trong danh sách S tại trạng thái được mô tả ở phần trước:

S[3]    NULL -------> 23                                        NULL
S[2]    NULL          23  ----------->  64                      NULL
S[1]    NULL          23    34          64 -> 78 -> 83          NULL 
S[0]    NULL    12    23    34    46    64    78    83    90    NULL

Giải thích:

Bước Tầng hiện tại Phần tử hiện tại Phần tử kế tiếp Di chuyển
1 S[3] NULL 23 Nhảy sang phần tử kế tiếp vì 23 <= K
2 S[3] 23 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
3 S[2] 23 64 Nhảy sang phần tử kế tiếp vì 64 <= K
4 S[2] 64 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
5 S[1] 64 78 Nhảy sang phần tử kế tiếp vì 78 <= K
6 S[1] 78 83 Nhảy sang phần tử kế tiếp vì 83 <= K
7 S[1] 83 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
8 S[0] 83 90 Dừng thuật toán vì 90 > K

Dựa vào giá trị của phần tử cuối cùng, chúng ta kết luận không tìm thấy giá trị 85 trong danh sách. Mặt khác, nếu chúng ta tìm K = 83, các bước duyệt trên danh sách sẽ giống hệt như vậy ngoại trừ việc thuật toán sẽ kết thúc ở bước thứ 7 và chúng ta tìm được K.

Để ý các bước duyệt, chúng ta thấy thuật toán đã “nhảy cóc” qua các phần tử 12, 34 và 46.

Thêm phần tử vào danh sách

Gọi H là giá trị của phần tử cần thêm vào danh sách S. Thuật toán được mô tả như sau:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0] tương ứng với tầng N-1, N-2, ... 1, 0.

  • Bước 2: Nếu H đã tồn tại trong danh sách S, kết thúc thuật toán.

  • Bước 3: Thêm phần tử giá trị H vào sau p[0].

  • Bước 4: Tung một đồng xu

    • Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (p[1] nếu là tầng 1, p[2] nếu là tầng 2, …..).

    • Nếu được mặt xấp, dừng thuật toán.

  • Bước 5: Quay lại bước 4.

Lưu ý tại bước 4, thuật toán phải tạo tầng mới nếu đồng xu hiện mặt ngửa và chúng ta đang ở tầng trên cùng.

Xóa phần tử khỏi danh sách

Gọi H là giá trị của phần tử cần phải xóa khỏi danh sách S. Thuật toán khá tương tự với việc thêm phần tử:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0]

  • Bước 2: Nếu không tìm thấy H, thuật toán kết thúc.

  • Bước 3: Ngược lại, xóa tất cả các phần tử tại vị trí p[N-1], p[N-2] … p[1], p[0] khỏi danh sách.

  • Bước 4: Xóa tất cả các tầng trống (tầng chỉ có hai phần tử NULL ở đầu và cuối)

Cài đặt

Chúng ta định nghĩa một phần tử của danh sách nhảy cóc như sau:

class SkipListNode(object):

    def __init__(self, value):
        self.value = value
        self.next  = None
        self.down  = None

Như các bạn thấy, với mỗi phần tử ngoài giá trị cần lưu, chúng ta chỉ quan tâm đến phần tử kế tiếp (bên phải) và phần tử tương ứng nằm ở tầng dưới.

Kế tiếp, định nghĩa danh sách nhảy cóc với hàm khởi tạo:

class SkipList(object):

    def __init__(self):
        self.head = SkipListNode(None)

Lớp SkipList sử dụng biến head để lưu phần tử đầu tiên của tầng cao nhất, đây luôn là vị trí bắt đầu khi chúng ta duyệt danh sách.

Dễ thấy rằng tác vụ Thêm và Tìm Kiếm đều cần phải duyệt qua danh sách với cùng một cách để tìm một giá trị, vì vậy chúng ta định nghĩa hàm _search để có thể dùng chung cho cả hai như sau:

    def _search(self, value):
        last_nodes   = []
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                current_node = current_node.next
            else:
                last_nodes.append(current_node)
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break
        return last_nodes

Cách hoạt động của hàm này được mô tả ở mục Tìm kiếm trong danh sách, giá trị trả về là danh sách p[N-1], p[N-2], ... p[0] tương ứng với phần tử cuối cùng được duyệt đến tại các tầng N-1, N-1, ... 0

Lúc này hàm search của chúng ta khá đơn giản, chỉ cần kiểm tra giá trị của phần tử cuối cùng được trả về bởi _search:

    def search(self, value):
        last_nodes = self._search(value)

        if last_nodes[-1].value == value:
            return value

        return None

Hàm insert để thêm phần tử vào danh sách:

    def insert(self, new_value):

        last_nodes = self._search(new_value)

        # Stop if the value is already there in the list
        if last_nodes[-1].value == new_value:
            return 

        last_created_node = None
        while True:
            new_node = SkipListNode(new_value)

            if len(last_nodes) > 0:
                last_node       = last_nodes.pop()
                new_node.next   = last_node.next
                last_node.next  = new_node
            else:
                new_head       = SkipListNode(None)
                new_head.down  = self.head
                new_head.next  = new_node
                new_node.next  = None
                self.head      = new_head

            new_node.down      = last_created_node
            last_created_node  = new_node

            # We are flipping the coin now 
            if random.randint(0, 1) != 0:
                break

Và cuối cùng là hàm remove để xóa phần tử khỏi danh sách:

    def remove(self, value):
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                if current_node.next.value < value:
                    current_node = current_node.next
                else: 
                    current_node.next = current_node.next.next

                if current_node.value is None and current_node.next is None\ 
                    and current_node.down is not None:
                    self.head = current_node.down
            else:
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break

Về cơ bản hàm này khá giống hàm _search: chúng ta vẫn duyệt từ head để tìm kiếm giá trị value. Điểm khác biệt là, nếu tìm thấy value ở bất kỳ tầng nào, chúng ta tiến hành xóa phần tử khỏi tầng đó đồng thời xóa luôn tầng này nếu không còn phần tử (khác NULL) nào khác.

Độ phức tạp

  • Trung bình:

    • Bộ nhớ cần thiết: O(n)

    • Thời gian tìm kiếm, thêm, xóa: O(logn)

  • Tệ nhất:

    • Bộ nhớ cần thiết: O(n*logn)

    • Thời gian tìm kiếm, thêm, xóa: O(n)

Bàn luận thêm

  • Các bạn có thể thấy ở thao tác Thêm phần tử, danh sách không thay đổi nếu chúng ta thêm một phần tử vốn đã có sẵn trong danh sách. Điều này đồng nghĩa với việc chúng ta mặc định các phần tử là đôi một khác nhau. Hãy sửa lại các đoạn mã ở trên để danh sách nhảy cóc của chúng ta có thể hỗ trợ các phần tử giống nhau.

  • Để ý rằng độ phức tạp của Danh Sách Nhảy Cóc tương đương với Cây Nhị Phân, ngoại trừ việc Danh Sách Nhảy Cóc sử dụng nhiều bộ nhớ hơn. Bạn đọc có thể chỉ ra điểm nhỉnh hơn của Danh Sách Nhảy Cóc không ? (Gợi ý: chuyện gì xảy ra đối với hai danh sách khi có nhiều tiến trình muốn thêm phần tử vào danh sách cùng một lúc ?)

  • Hãy viết hàm in ra trạng thái của danh sách nhảy cóc.

  • Hãy viết hàm in ra các phần tử của danh sách nhảy cóc.

Chương trình đường hầm HTTP bằng Python

written by Phan Đắc Anh Huy, on Jan 14, 2014 1:43:00 AM.

(Bài gửi đến PCNV từ cộng tác viên Vũ Khuê. Xin cảm ơn bạn.)

Giới thiệu

Có những lúc bạn cần kết nối đến máy chủ ngoài mạng nội bộ ở một cổng không thuộc những giao thức ứng dụng phổ biến như HTTP hay HTTPS (cổng 80 hoặc 443). Nhưnng điều đáng buồn là tường lửa chặn yêu cầu đến những cổng ngoài 80 hoặc 443. Khi đó, điều bạn có thể làm là thiết lập một chương trình trên một máy ngoại mạng. Chưong trình này nhận yêu cầu tử cổng 80 hoặc 443 và chuyển nó đến cổng và máy chủ thực sự. Việc này thường được gọi là thiết lập đường hầm (tunneling).

Trên thực tế, chương trình ssh với tuỳ chọn -L thường được sử dụng cho nhiệm vụ này. Tuy nhiên trong bài này chúng ta sẽ viết chương trinh đường hầm này dựa trên giao thức HTTP. Mục đích chính là miêu tả việc xử lý dữ liệu mạng tầm thấp với Python.

Cấu trúc

Chương trình này gồm 2 thành phần máy khách (client) và máy chủ (server)

  • Tunnel.py: thành phần máy khách. Thành phần này nhận yêu cầu từ một cổng nhất định và bọc dữ liệu này duới dạng một yêu cầu HTTP rồi gửi đến thành phần máy chủ.
  • Tunneld.py: thành phần máy chủ. Thành phần thực chất là một máy chủ HTTP (HTTP server). Khi có yêu cầu gửi đến, nó sẽ đọc yêu cầu này và thực hiện tác vụ tương ứng. Ví dụ như thực hiện kết nối với một máy khác hoặc chuyển dữ liệu từ tải của yêu cầu HTTP đến máy này.

Để thiết lập đường hầm, chạy 2 thành phần như sau:

python tunnel.py -p [client_listen_port] -h [target_host]:[target_port]
python tunneld.py -p [server_listen_port]

Một ứng dụng muốn gửi yêu cầu đến máy nào đó (target_host), nó cần gửi yêu cầu đó thông qua cổng mà tunnel.py được khởi tạo với (client_listen_port).

Triển khai

Bạn có thể tìm thấy mã chương trình tại đây: https://github.com/khuevu/http-tunnel.

Tunnel.py

Thành phần này nghe ở một cổng nhất định. Nó có 2 tiểu trình (thread) riêng biệt để nhận và trả lời yêu cầu:

	...
	BUFFER = 1024 * 50

	#set global timeout
	socket.setdefaulttimeout(30)

	class SendThread(threading.Thread):

	    """
	    Thread to send data to remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	        	# receive data and send to through tunnel
	            data = self.socket.recv(BUFFER)
	            self.conn.send(data)
	    ...

	class ReceiveThread(threading.Thread):

	    """
	    Thread to receive data from remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	            data = self.conn.receive()
	            self.socket.sendall(data)

	    ...

Hằng số BUFFER là lượng dữ liệu theo byte mà chường trình sẽ nhận từ ứng dụng trước khi gửi qua đường hầm. Có thể có nhiều ứng dụng kết nối với chương trình tunnel.py. Vì thế, ta cần tạo kết nối riêng cho mỗi ứng dụng. Dưới đây là đoạn mã của lớp Connection:

class Connection():
    
    def __init__(self, connection_id, remote_addr):
        self.id = connection_id
        self.http_conn = httplib.HTTPConnection(remote_addr['host'], remote_addr['port'])
    ...

    def create(self, target_addr):
        params = urllib.urlencode({"host": target_addr['host'], "port": target_addr['port']})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}

        self.http_conn.request("POST", self._url("/" + self.id), params, headers)

        response = self.http_conn.getresponse()
        response.read()
        if response.status == 200:
            print 'Successfully create connection'
            return True 
        else:
            print 'Fail to establish connection: status %s because %s' % (
                response.status, response.reason)
            return False 

    def send(self, data):
        params = urllib.urlencode({"data": data})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}
        try: 
            self.http_conn.request("PUT", self._url("/" + self.id), params, headers)
            response = self.http_conn.getresponse()
            response.read()
            print response.status 
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Sending Data: %s" % ex

    def receive(self):
        try: 
            self.http_conn.request("GET", "/" + self.id)
            response = self.http_conn.getresponse()
            data = response.read()
            if response.status == 200:
                return data
            else: 
                print "GET HTTP Status: %d" % response.status
                return ""
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Receiving Data: %s" % ex
            return "" 

    ...

Như bạn thấy ở đây, Connection có những hàm để thiết lập đường hầm, gửi và nhận dữ liệu. Sự tưong tác này được xây dựng trên giao thức HTTP. Cụ thể là:

  • POST request: yêu cầu thiết lập kết nối.
  • PUT request: gửi dữ liệu qua kết nối.
  • GET request: nhận kết nối.
  • DELETE request: kết thúc kết nối.

Sẽ rõ ràng hơn khi ta nhìn vào mã của tunneld.py, thành phần nhận những yêu cầu HTTP này:

class ProxyRequestHandler(BaseHTTPRequestHandler):
    ...

    BUFFER = 1024 * 50 

    def _get_connection_id(self):
        return self.path.split('/')[-1]
    ...

    def do_GET(self):
        """GET: Read data from TargetAddress and return to client through http response"""
        s = self._get_socket()
        if s:
            try:
                data = s.recv(self.BUFFER)
                print data
                self.send_response(200)
                self.end_headers()
                if data:
                    self.wfile.write(data)
        ...

    def do_POST(self):
        """POST: Create TCP Connection to the TargetAddress"""
        id = self._get_connection_id() 

        length = int(self.headers.getheader('content-length'))
        req_data = self.rfile.read(length)
        params = cgi.parse_qs(req_data, keep_blank_values=1) 
        target_host = params['host'][0]
        target_port = int(params['port'][0])

        print 'Connecting to target address: %s % s' % (target_host, target_port)
        #open socket connection to remote server
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect((target_host, target_port))
        s.settimeout(7)
        print 'Successfully connected'
        #save socket reference
        self.sockets[id] = s
        try: 
            self.send_response(200)
            self.end_headers()
        except socket.error, e:
            print e

    def do_PUT(self):
        """Read data from HTTP Request and send to TargetAddress"""
        id = self._get_connection_id()
        s = self.sockets[id]
        length = int(self.headers.getheader('content-length'))
        data = cgi.parse_qs(self.rfile.read(length), keep_blank_values=1)['data'][0] 
        try: 
            s.sendall(data)
            self.send_response(200)
        ...

    def do_DELETE(self): 
        self._close_socket()
        self.send_response(200)
        self.end_headers()

Ở đây, ProxyRequestHandler chính là một máy chủ HTTP, nhận và xử lý những yêu cầu cơ bản của HTTP.

  • do_POST: hàm này xử lý những yêu cầu POST. Nó sẽ lấy thông tin về máy đối tượng (tên miền, cổng) và tạo kết nối TCP đến máy đó. Nó trả về trạng thái 200 nếu kết nối này thành công.
  • do_GET: hàm này lấy dữ liệu từ kết nối đã được thiết lập với máy đối tương trong do_POST. Sau đó nó trả dữ liệu này trong trả lời HTTP của yêu cầu GET.
  • do_PUT: hàm này lấy nhận yêu cầu PUT, đọc dữ liệu từ tải của yêu cầu đó và gửi qua kết nối nói trên.
  • do_DELETE: hàm này đóng kết nối với máy đối tượng.

Thử nghiệm chương trình

Chúng ta sẽ thử chương trình này bằng việc kết nối với một IRC server thông qua chương trình. Trước hết, thiết lập đường hầm cần thiết. Tại một máy ngoại mạng, không bị chặn bởi tường lửa, chạy:

python tunneld.py -p 80

Tại máy nội mạng chạy:

python tunnel.py -p 8889 -h mayngoaimang:80 irc.freenode.net:6667

Như vậy ta đã thiết lập một đương hầm ở cổng 8889 qua máy ngoại mạng đến IRC server ở cổng 6667. Yêu cầu đến cổng 6667 thường bị chặn bởi tường lửa. Để thử nghiệm, ta kết nối đến cổng 8889 và gửi yêu cầu theo giao thức IRC:

nc localhost 8889
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz

(nc - netcat - là một công cụ giúp bạn gửi giữ liệu trên TCP: http://www.irongeek.com/i.php?page=backtrack-3-man/netcat).

Ta nhận được trả lời thông báo kết nối thành công:

:calvino.freenode.net NOTICE * :*** Looking up your hostname...
:calvino.freenode.net NOTICE * :*** Checking Ident
:calvino.freenode.net NOTICE * :*** Found your hostname
:calvino.freenode.net NOTICE * :*** No Ident response
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz
:calvino.freenode.net 001 abcxyz :Welcome to the freenode Internet Relay Chat Network abcxyz
:calvino.freenode.net 002 abcxyz :Your host is calvino.freenode.net[ ... /6667], running version ircd-seven-1.1.3
:calvino.freenode.net 003 abcxyz :This server was created Sun Dec 4 2011 at 14:42:47 CET
:calvino.freenode.net 004 abcxyz calvino.freenode.net ircd-seven-1.1.3 DOQRSZaghilopswzCFILMPQbcefgijklmnopqrstvz bkloveqjfI
:calvino.freenode.net 005 abcxyz CHANTYPES=# EXCEPTS INVEX CHANMODES=eIbq,k,flj,CFLMPQcgimnprstz CHANLIMIT=#:120 PREFIX=(ov)@+ MAXLIST=bqeI:100 MODES=4 NETWORK=freenode KNOCK STATUSMSG=@+ CALLERID=g :are supported by this server
:calvino.freenode.net 005 abcxyz CASEMAPPING=rfc1459 CHARSET=ascii NICKLEN=16 CHANNELLEN=50 TOPICLEN=390 ETRACE CPRIVMSG CNOTICE DEAF=D MONITOR=100 FNC TARGMAX=NAMES:1,LIST:1,KICK:1,WHOIS:1,PRIVMSG:4,NOTICE:4,ACCEPT:,MONITOR: :are supported by this server
:calvino.freenode.net 005 abcxyz EXTBAN=$,arx WHOX CLIENTVER=3.0 SAFELIST ELIST=CTU :are supported by this server
:calvino.freenode.net 251 abcxyz :There are 232 users and 70582 invisible on 31 servers
:calvino.freenode.net 252 abcxyz 45 :IRC Operators online
:calvino.freenode.net 253 abcxyz 10 :unknown connection(s)
:calvino.freenode.net 254 abcxyz 34513 :channels formed
:calvino.freenode.net 255 abcxyz :I have 6757 clients and 1 servers
:calvino.freenode.net 265 abcxyz 6757 10768 :Current local users 6757, max 10768
:calvino.freenode.net 266 abcxyz 70814 83501 :Current global users 70814, max 83501
:calvino.freenode.net 250 abcxyz :Highest connection count: 10769 (10768 clients) (2194912 connections received)
...

Kết

Như vậy chúng ta đã đi qua một chương trình xử lý dữ liệu mạng với Python. Chương trình chủ yếu làm việc với dữ liệu thông qua socket API. Một điều quan trọng khác mà bài viết này đề cập đến là sự tách biệt giữa giao thức ứng dụng và dữ liệu gửi trên giao thức đó. Chúng ta có thể vận chuyển dữ liệu mà thông thường đuợc gửi bằng giao thức này qua một giao thức khác.

Chú ý: Chương trình chỉ có mục đích thí nghiệm và không phù hợp với chạy thực dụng.

Thuật toán đẹp: Tìm chuỗi Boyer-Moore-Horspool

written by Nguyễn Thành Nam, on Jan 9, 2014 2:35:00 PM.

Mục đích

Tìm chính xác (exact match) chuỗi con (substring) trong một chuỗi dài hơn.

Ý tưởng chính

Gọi chuỗi cần tìm là P (pattern), và chuỗi dài là T (text).

So sánh ngược P trong T, nghĩa là ta sẽ so sánh ký tự cuối của P trước, sau đó so sánh ký tự kế cuối, và lần lượt như vậy đến ký tự đầu tiên trong P. Gọi vị trí trong T để bắt đầu so sánh hai chuỗi là i. Việc so sánh sẽ so sánh lần lượt T[i] với ký tự cuối của P, rồi T[i-1] với ký tự kế cuối của P, v.v...

Nếu việc so sánh ngược vượt qua được ký tự đầu tiên trong P, ta đã tìm được P trong T.

Nếu việc so sánh ngược bị thất bại, ta sẽ căn P cho khớp với T[i] và thử lại việc so sánh ngược. Điều này tương đương với việc dịch chuyển i đến vị trí xa hơn trong T. Đây là ý tưởng chủ chốt của thuật toán BMH.

  • Nếu T[i] không có trong P, thì ta có thể dịch chuyển i đến vị trí i + len(P).
  • Nếu vị trí cuối cùng của T[i] trong P là x thì ta dịch chuyển i đến vị trí i + len(P) - x - 1.
Trạng thái bắt đầu

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
           = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh sai

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
         ! = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

Căn P theo T[i]...

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             |
          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

------------------------------------------

... cũng có nghĩa là dịch chuyển i

                   i
                   |
                   v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

Để cài đặt hai bước trên, người ta thường dùng một mảng chứa vị trí cuối cùng của các ký tự trong P trừ ký tự cuối cùng (P[ : -1]).

Ví dụ

Giả sử chúng ta muốn tìm chuỗi needle trong chuỗi find the needle in the haystack.

Trước khi bắt đầu, ta sẽ lập bảng vị trí cuối của các ký tự trong P[ : -1].

Ký tựVị tríDiễn giải
n0
e2Ta chọn vị trí của ký tự thứ hai.
d3
l4

Và sự thay đổi ở các bước của thuật toán. Vì độ dài của P là 6, nên i sẽ bắt đầu từ vị trí 5. Trong bảng dưới, chữ đậm là ký tự trùng nhau của T và P, chữ gạch dưới là các ký tự đang xét.

iTT[i]Diễn giải
5find the needle in the haystacktt không có trong bảng. Dịch i lên 11 (5 + 6).
11find the needle in the haystackee có trong bảng. Dịch i lên 14 (11 + 6 - 2 - 1).
14find the needle in the haystackeTìm thấy. e có trong bảng. Dịch i lên 17 (14 + 6 - 2 - 1).
17find the needle in the haystacknn có trong bảng. Dịch i lên 22 (17 + 6 - 0 - 1).
22find the needle in the haystackkhoảng trắngkhoảng trắng không có trong bảng. Dịch i lên 28 (22 + 6).
28find the needle in the haystackaa không có trong bảng. Dịch i lên 34 (28 + 6). Dừng việc tìm kiếm vì đã xét hết chuỗi.

Độ phức tạp

Thời gian chạy: Tệ nhất là O(n*m), với n là độ dài của T và m là độ dài của P. Trung bình là O(n). Và tốt nhất là dưới tuyến tính (sublinear) vì thuật toán có thể nhảy qua nhiều ký tự. Trong ví dụ trên, ta chỉ cần 12 phép so sánh để tìm chuỗi needle (6 ký tự) trong chuỗi find the needle in the haystack (31 ký tự).

Bộ nhớ cần thiết: O(n) với n là số ký tự trong bảng chữ cái (ví dụ như 256 giá trị của một byte, hoặc nếu bảng chữ cái là Unicode thì có thể sẽ nhiều hơn 60000 giá trị) vì chúng ta cần tạo bảng vị trí các ký tự trong P.

Thuật toán BMH là thuật toán tìm chuỗi chính xác tổng quát nhất, nhanh nhất, và đơn giản nhất.