Đếm chuỗi con xuôi ngược trong thời gian O (n)

Question

Cho một xâu (giả chỉ ký tự tiếng Anh) S chiều dài n, chúng ta có thể đếm số lượng các chuỗi con xuôi ngược với các thuật toán sau đây:

for i = 0 to |S| do 
    p1 = number of palindromes centered in i (odd length) 
    p2 = number of palindromes centered in i and i+1 (even length) 

    add p1 + p2 to total number of palindromic substrings of S 

Đoạn mã trên là O(n^2) Tuy nhiên.

Tôi quan tâm đến thuật toán giải quyết vấn đề này trong O(n). Tôi biết chắc chắn rằng một trong những tồn tại như tôi đã nghe nhiều người nói rằng nó, và vấn đề tồn tại trên một trang web trực tuyến thẩm phán địa phương với một ràng buộc trên của 1 000 000 trên n, tuy nhiên tôi chưa bao giờ nhìn thấy các thuật toán và không thể dường như có thể tìm ra nó.

Cập nhật:

Ý tưởng chung tôi có là để tính toán len[i] = length of the longest palindrome centered at the character 2i + 1 và một mảng tương tự cho palindromes thậm chí dài. Với sổ sách kế toán tốt, nó có thể tính toán điều này trong O(1) cho mỗi nhân vật, mà sẽ cho phép chúng ta đếm rất nhiều palindromes cùng một lúc. Tôi đang mắc kẹt về cách chính xác để tính toán này tuy nhiên.

Tôi sẽ chấp nhận giải pháp sử dụng O(n) và thậm chí có thể là O(n log n) bộ nhớ bổ sung. Tôi nghĩ điều này là không thể nếu không có nó.

Bất kỳ ý tưởng hay tham chiếu hay nào đều được đánh giá cao.

Answer 1

Trang sau hiển thị thuật toán để tính toán chuỗi con palindromic dài nhất trong thời gian O (n) và thực hiện bằng cách tính chuỗi con palindromic dài nhất tại mọi trung tâm có thể và sau đó lấy tối đa. Vì vậy, bạn sẽ có thể dễ dàng sửa đổi nó cho các mục đích của bạn.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

EDIT: Liên kết đầu tiên trông một chút run rẩy khi xem xét kỹ, vì vậy đây là một khác:

http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829

Answer 2

Đối với chuỗi "bình thường" nó nên được khá hiệu quả để nhìn vào mỗi nhân vật là "trung tâm" tiềm năng của một palindrome và sau đó kiểm tra xem các nhân vật xung quanh thực sự xây dựng một:

# check odd palindromes 
for center in range(len(ls)): 
    # check how many characters to the left and right of |center| 
    # build a palindrome 
    maxoffs = min(center, len(ls)-center-1) 
    offs = 0 
    while offs <= maxoffs and ls[center-offs] == ls[center+offs]: 
     offs += 1 
    offs -= 1 
    print ls[center-offs : center+offs+1]          

# check for even palindromes 
for center in range(len(ls)-1): 
    maxoffs = min(center, len(ls)-center-2) 
    offs = 0 
    while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]: 
     offs += 1 
    offs -= 1 
    if offs >= 0: 
     print ls[center-offs : center+offs+2] 

Đối với chuỗi bình thường này nên là về O (n), mặc dù trong trường hợp xấu nhất, ví dụ nếu chuỗi chỉ bao gồm một ký tự lặp đi lặp lại, nó vẫn sẽ mất thời gian O (n).

Answer 3

Xem xét một chuỗi S="aaabb".

Nối một ký tự '$' ở cả hai đầu của chuỗi và giữa hai ký tự liên tiếp để thay đổi chuỗi thành S="$a$a$a$b$b$" và áp dụng Manacher's algorithm cho chuỗi này S.

Chuỗi mới S có chiều dài 2n + 1 cho chúng ta thời gian chạy O (2n + 1) giống với O (n).

index : 1 2 3 4 5 6 7 8 9 10 11 
A  : 1 3 5 7 5 3 1 3 5 3 1 
S  : $ a $ a $ a $ b $ b $ 

Mảng A là kết quả của thuật toán của Manacher.

Bây giờ, tổng của A[i]/4 cho chỉ số nơi '$', khác (A[i]+1)/4 cho mỗi nhân vật khác từ 1 < = i < = n là câu trả lời của bạn.

Ở đây, $ hoạt động như một trung tâm cho các bản nền palidromic dài và chiều dài lẻ có thể được tính toán bình thường. Câu trả lời cho trường hợp này là:

0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 = 9 (a, a, aaa, a, b, b, aa , aa, bb).