- Đọc các ký tự của chuỗi theo thứ tự. Điền vào một mảng với các chỉ số của ký tự đầu tiên của mỗi lần chạy các ký tự liên tiếp, thời lượng chạy, và liệu ký tự đó có bằng ký tự thứ 2 trước đó gặp phải hay không. Gọi mảng này A. Theo dõi tổng số đang chạy và khởi tạo nó bằng không. gọi đây là x.
ví dụ, abbaabbccd => [(0,1, ), (1,2,), (3,2, T), (5,2, T), (7,2, F), (9,1, F)] = A
- Đối với mỗi chỉ số i trong A, tìm chỉ mục j bạn nhận được bằng cách di chuyển sang phải 1, sau đó tiếp tục di chuyển sang phải chừng nào bạn còn đất trên các yếu tố 'Đúng' của A.
ví dụ: nếu i = 0, thì j = 3 vì (5,2, T) là đúng, nhưng (7,2, F) là sai.
- Cho x = x + (A [i] [1]) * (Sum từ k = i + 1 tới j của A [k] [1])
ví dụ như, tiếp tục i = 0, chúng tôi nhận được 1 * 6 = 6. Điều này tương ứng với tất cả các chuỗi 6 'ab ...' bắt đầu bằng 'a'.
- Bây giờ, thời gian chạy là gì? Vâng, lưu ý ở bước 2, bạn tìm thấy j bằng cách di chuyển sang phải qua một loạt các phần tử thực sự cho đến khi bạn tìm thấy một phần tử sai. Yếu tố đó vẫn cố định cho đến khi i = j, tại thời điểm đó nó di chuyển sang phải một lần nữa. Chúng ta có hai chỉ số di chuyển đơn điệu về bên phải, do đó, việc xử lý A là tuyến tính trong A là tuyến tính trong đầu vào.
Để kết thúc ví dụ này: (bắt đầu với x = 0)
- i = 0, j = 3, x + = 6 -> x = 6
- i = 1, j = 3, x + = 8 -> x = 14
- i = 2, j = 3, x + = 4 -> x = 18
- i = 3, j = 4, x + = 4 -> x = 22
- i = 4, j = 5, x + = 2 -> x = 24
Tôi nên đề cập đến, bạn không tính tổng từ i + 1 đến j mỗi lần, bạn chỉ cần giảm số tiền theo số tiền thích hợp mỗi khi bạn tăng i và chỉ tính toán lại khi j tăng.
chắc. Với một chuỗi có tối đa hai ký tự duy nhất, bạn có thể tìm hiểu xem có bao nhiêu phần tử không trống không? Trong số đó, có bao nhiêu chỉ có một nhân vật duy nhất? Phần còn lại phải có chính xác hai. –
@ n.m. Tôi chỉ cần một số, không phải là một bộ chứa tất cả các chất nền thỏa mãn điều kiện. Đó là một vấn đề O (2^n). Tôi nghĩ rằng cách của bạn được dựa trên tôi đã có tất cả các chất nền có chứa tối đa hai nhân vật độc đáo. – Jun
Bạn có thể viết một ví dụ đầu vào và đầu ra? – Dialecticus