Giải thuật Manacher - Tìm xâu con đối xứng dài nhất với độ phức tạp tuyến tính

Bài gốc:

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

Longest Palindromic String – Xâu con Đối xứng Dài nhất | Phần 1

Bài toán: Cho một xâu, hãy tìm xâu con đối xứng dài nhất (LPS).

Ví dụ: Với xâu “forgeeksskeegfor” thì LPS là “geeksskeeg”

Cách 1 (Brute Force – Duyệt trâu bò)

Cách này chỉ đơn giản là xét từng xâu con có đối xứng hay không.

Chạy 3 vòng lặp với 2 vòng là tìm (từng bước một) chỉ số đầu và cuối của xâu con và 1 vòng là xét xâu con có đối xứng không.

Độ phức tạp thời gian:       O(n^3)

Độ phức tạp phụ:             O(1)

Code Java

Cách 2 (Dynamic Programning – Quy hoạch động)

Giảm độ phức tạp bằng cách chứa các kết quả phụ.

Bảng boolean table[n][n] được đổ dần từ dưới lên.

table[i][j]=true nếu xâu con từ i đến j đối xứng, và ngược lại

Thuật toán:

Gọi k là độ dài xâu con đối xứng đang xét

+ table[i][i]=true với mọi i (k=1)

+ check các vị trí table[i][i+1] (k=2)

+ với k=3:

- nếu table[i+1][j-1]==true và s[i]==s[j] thì table[i][j]=true.

- và ngược lại

Độ phức tạp thời gian:       O(n^2)

Không gian nhớ phụ:          O(n^2)

Code Java

Cách 3: Sinh ra tất cả các xâu đối xứng và lưu vết LPS

+ Sinh PS độ dài lẻ: từ tâm khai triển ra hai hướng để tìm LPS

+ Sinh PS độ dài chẵn: từ hai tâm khai triển ra hai hướng để tìm LPS

Độ phức tạp thời gian:       O(n^2)

Không gian nhớ phụ:          O(1)

Code Java

Thuật toán Manacher – Tìm LPS với thời gian tuyến tính | Phần 1

Như đã nói, có thể tìm PS bằng cách khai triển ra hai hướng từ tâm.

+ Với PS độ dài lẻ:

Ví dụ, với xâu “abababa”

ở đây tâm là ký tự thứ 4 (chữ “b” màu đỏ). Các kí tự bên trái và phải cách tâm cùng độ dài tương ứng nhau nên xâu này đối xứng

(các kí tự tưong ứng nhau có cùng màu)   

+ Với PS độ dài chẵn:

Ví dụ, với xâu “abaaba”

ở đây coi vị trí giữa hai ký tự là tâm (dấy gạch màu đỏ). Các kí tự bên trái và phải cách tâm cùng độ dài tương ứng nhau nên xâu này đối xứng

(các kí tự tưong ứng nhau có cùng màu)   

Để tìm LPS của xâu s có độ dài N, có một cách là lấy 2*N+1 tâm (với N ký tự, N-1 vị trí giữa hai kí tự và 2 vị trí ngoài cùng). Với mỗi vị trí, ta giả sử nó là tâm rồi xét từng cặp ký tự theo hai hướng trái phải với từng tâm ấy, có lưu vết để tìm LPS