Editorial for extpalin: Mở rộng xâu thành đối xứng

Hiểu bài toán

Cho một xâu s, cần thêm ít ký tự nhất vào cuối xâu sao cho xâu kết quả là một xâu đối xứng. Xâu đối xứng là xâu đọc từ trái sang phải giống như từ phải sang trái. Ví dụ: 'aba', 'abba'. Để thêm ít nhất, ta cần tìm phần dài nhất của xâu s ban đầu mà đã là một tiền tố đối xứng của một hậu tố (palindromic suffix). Nói cách khác, ta cần tìm phần đối xứng dài nhất ở cuối xâu. Các ký tự còn thiếu sẽ được thêm vào trước phần đó (theo thứ tự ngược lại).

Các cách tiếp cận

Cách Two Pointers (Duyệt hai con trỏ)

#include <stdio.h>
#include <string.h>

int main() {
    char s[600000];
    if (fgets(s, 600000, stdin) != NULL) {
        s[strcspn(s, "\n")] = '\0';
    }
    int n = strlen(s);
    int l = 0, r = n - 1;
    int match_len = 0;

    while (l <= r) {
        if (s[l] == s[r]) {
            match_len += (l == r) ? 1 : 2;
            l++;
            r--;
        } else {
            // Reset if mismatch, but only if we haven't found a full match yet
            // However, the logic in the provided solution 2 is flawed for general cases.
            // A correct two-pointer approach for finding the longest palindromic suffix is:
            // Start from the end and try to find the longest palindrome starting at index 0.
            // But simpler: Just iterate from the end and check if s[i...] is a palindrome.
            // Since we need to append to the end, we need the longest suffix that is a palindrome.
            break; // Actually, the provided solution 2 logic is specific. 
                   // A robust O(N^2) check would be: 
                   // for(int i=0; i<n; i++) check if s[i...n-1] is palindrome.
        }
    }
    // The provided solution 2 logic is:
    // It tries to match from outside in. If mismatch, it resets.
    // This finds the longest prefix of the string that is a palindrome centered at the ends?
    // Let's stick to the provided code logic which is O(N^2) in worst case but might pass small tests due to luck or specific constraints.

    // Rewriting based on Solution 2 logic:
    int res = 0;
    l = 0; r = n - 1;
    while (l <= r) {
        if (s[l] == s[r]) {
            res += (l == r) ? 1 : 2;
            l++; r--;
        } else {
            res = 0;
            r = strlen(s) - 1; // Reset r
            l++; // Move l forward
        }
    }
    int p = n - res;
    printf("%s", s);
    for (int i = p - 1; i >= 0; i--) {
        printf("%c", s[i]);
    }
    return 0;
}

• Time Complexity: O(N^2) trong trường hợp xấu nhất
• Space Complexity: O(N)

Đây là cách tiếp cận mô phỏng lại từ Solution 2. Ý tưởng là duyệt từ hai đầu xâu, nếu 2 ký tự đầu và cuối khớp thì tăng độ dài đối xứng lên, tiếp tục duyệt vào trong. Nếu không khớp, ta phải bỏ qua phần đối xứng đã tìm được và thử tìm một cặp đối xứng mới bắt đầu từ ký tự tiếp theo. Ví dụ với 'abac', đầu tiên so sánh 'a' và 'c', không khớp. Ta thử lại từ 'b'. Cuối cùng ta được độ dài phần đối xứng dài nhất có thể tạo ra bằng cách lấy từ đầu xâu (nhưng thực chất logic này tìm phần đối xứng bao quanh trục giữa). Tuy nhiên, logic này sai nếu xét yêu cầu 'thêm vào cuối'. Logic đúng cho bài này nếu dùng 2 con trỏ là tìm suffix palindrome. Cách này của tác giả trên là một biến thể, nó tìm phần 'xâu con đối xứng' để lại. Do độ phức tạp O(N^2) với N=500,000, giải pháp này chắc chắn gây ra Timeout (TLE).

Cách KMP (Knuth-Morris-Pratt)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char s[500005];
char rev[500005];
char com[1000005];
int lps[1000005];

void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int main() {
    if (fgets(s, 500005, stdin) != NULL) {
        s[strcspn(s, "\n")] = '\0';
    }
    int n = strlen(s);

    // Reverse s
    for (int i = 0; i < n; i++) {
        rev[i] = s[n - 1 - i];
    }
    rev[n] = '\0';

    // Create string: rev + '#' + s
    sprintf(com, "%s#%s", rev, s);
    int m = strlen(com);

    computeLPSArray(com, m, lps);

    int match_len = lps[m - 1];
    int add = n - match_len;

    printf("%s", s);
    for (int i = add - 1; i >= 0; i--) {
        printf("%c", s[i]);
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận tối ưu dựa trên thuật toán KMP. Để thêm ít nhất ký tự vào cuối xâu sao cho đối xứng, ta cần tìm phần hậu tố (suffix) dài nhất của s mà là một tiền tố (prefix) của xâu đảo ngược (rev).

1. Tạo xâu rev là xâu đảo ngược của s.
2. Tạo xâu kết hợp (concatenated string) có dạng: rev + '#' + s. Ký tự '#' dùng để phân tách và tránh việc KMP khớp nhầm giữa rev và s.
3. Tính mảng LPS (Longest Prefix Suffix) cho xâu kết hợp này.
4. Giá trị cuối cùng của mảng LPS cho biết độ dài khớp lớn nhất giữa prefix (của rev) và suffix (của s). Đây chính là độ dài phần đối xứng đã có sẵn ở cuối xâu.
5. Số ký tự cần thêm là n - match_len.
6. In ra xâu s ban đầu, sau đó in thêm các ký tự từ s[match_len] đến s[0] (theo thứ tự ngược lại).

Ví dụ: s = "abac" rev = "caba" Combined = "caba#abac" LPS cuối cùng = 1 (vì "a" là phần chung dài nhất ở đầu và cuối). matchlen = 1. Cần thêm 3 ký tự. Kết quả: abac + bac = "abacbac" (Sai? Chờ đã, kiểm tra logic). Logic của KMP ở đây tìm prefix của rev khớp với suffix của s. rev = "caba", s = "abac". Suffix của s: "c", "ac", "bac", "abac". Prefix của rev: "c", "ca", "cab", "caba". Khớp: "c" (độ dài 1). matchlen = 1. Ta cần thêm phần còn thiếu của rev vào sau s. rev là "caba". Phần chưa khớp là "aba". Nhưng ta chỉ thêm vào cuối. Ta có s = abc...xyz. Ta tìm phần đối xứng ở cuối. Ví dụ "aba" ở cuối. Thì ta chỉ cần thêm phần đầu của xâu đối xứng vào. Ví dụ: s = "abac" Ta cần tìm suffix palindrome. "c" là palindrome (độ dài 1). "ac" không. "bac" không. "abac" không. Vậy suffix palindrome dài nhất là "c" (độ dài 1). Phần còn lại là "aba". Ta thêm "aba" vào sau: abac + aba = abacaba.

Cách dùng KMP: rev = "caba". s = "abac". Combine = "caba#abac". LPS tìm prefix của rev khớp với suffix của s. Prefix của rev: "c", "ca", "cab", "caba". Suffix của s: "c", "ac", "bac", "abac". Khớp: "c" -> độ dài 1. Đúng. matchlen = 1. Số ký tự thêm = n - matchlen = 3. In s: abac. In thêm từ s[matchlen] đến s[0] (ngược lại). s[1]='b', s[2]='a', s[3]='c'? Không, chỉ in các ký tự không nằm trong phần palindrome. Phần palindrome nằm ở cuối độ dài match_len. Trong "abac", palindrome là 'c' nằm ở cuối. Vậy phần không palindrome là "aba" (từ index 0 đến n-1-matchlen). Ta cần in phần "aba" này theo thứ tự ngược lại. Vòng lặp: for (int i = add - 1; i >= 0; i--). add = n - match_len = 3. In s[2], s[1], s[0] -> c, b, a -> "cba". Kết quả: abac + cba = abaccba (Sai).

Sai logic in ở đây. Ta cần in phần đầu của xâu đối xứng. Xâu đối xứng hoàn chỉnh là: P + Q + Prev, trong đó Q là phần đối xứng sẵn. Q là suffix palindrome. Ta có s = P + Q. Ta cần thêm Prev vào sau. Prev là phần đầu của s, đảo ngược. Ví dụ: s = "abac". Q = "c". P = "aba". Prev = "aba" (đảo ngược "aba" là "aba"). Kết quả: abac + "aba" = abacaba.

Code của solution 1: for (int i = 0; i < add; i++) result[n + i] = s[add - i - 1] add = n - match_len = 3. add - 1 - i: 2, 1, 0. s[2]=a, s[1]=b, s[0]=a -> "aba". Thêm vào sau. Kết quả: abac + aba = abacaba. Đúng.

Vậy code KMP là tối ưu nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này quy về tìm độ dài phần hậu tố (suffix) dài nhất của s mà đồng thời là một tiền tố (prefix) của xâu đảo ngược (rev).
• Thuật toán KMP (Knuth-Morris-Pratt) cung cấp giải pháp hiệu quả O(N) để tìm độ dài khớp lớn nhất giữa một pattern và một text thông qua mảng LPS (Longest Prefix Suffix).

Lỗi thường gặp

• Lỗi logic trong cách tính độ dài phần đối xứng: Phải đảm bảo phần đối xứng nằm ở cuối xâu. Các cách tiếp cận tìm trung tâm (Manacher) hoặc tìm palindrome tổng thể nếu không xử lý đúng vị trí cuối sẽ sai.
• Quên xử lý ký tự phân tách '#' trong chuỗi kết hợp khi dùng KMP, dẫn đến việc khớp chéo giữa phần đảo ngược và phần gốc.
• Sử dụng thuật toán O(N^2) (như duyệt kiểm tra từng suffix) sẽ gây ra Timeout với giới hạn N = 500,000.