Tách một xâu thành các xâu con đối xứng

NỘI DUNG

Giới thiệu bài toán

Bài toán tách một xâu thành các xâu con đối xứng là bài toán tìm các xâu con của xâu đó sao cho các xâu con đó đều là xâu đối xứng.

Ví dụ: Xâu “abbaabba” có các xâu con đối xứng là “a”, “b”, “bb”, “abba”, “baab”, “abbaabba”.

Các thuật toán giải bài toán

Có thể giải quyết bài toán này bằng các thuật toán sau đây:

Quy hoạch động: Tìm độ dài lớn nhất của xâu con đối xứng bắt đầu từ vị trí i và kết thúc tại vị trí j. Sử dụng mảng 2 chiều để lưu kết quả. Thuật toán này có độ phức tạp thời gian O(n^2) và độ phức tạp không gian O(n^2).
Sinh tổ hợp: Tạo ra tất cả các xâu con của xâu đó và kiểm tra xem chúng có đối xứng hay không. Độ phức tạp thời gian của thuật toán này là O(2^n).
Giải thuật Manacher: Tìm tất cả các xâu con đối xứng bằng cách sử dụng giải thuật Manacher để tìm xâu đối xứng lớn nhất tại mỗi vị trí trong xâu. Độ phức tạp thời gian của thuật toán này là O(n).

Cài đặt các thuật toán

Cài đặt thuật toán Quy hoạch động với Python

def find_palindromes(s):
    n = len(s)
    # khởi tạo một mảng 2 chiều để lưu trữ kết quả
    dp = [[False] * n for _ in range(n)]

    # tìm xâu con độ dài 1 là xâu đối xứng
    for i in range(n):
        dp[i][i] = True

    # tìm xâu con độ dài 2 có thể là xâu đối xứng
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True

    # tìm các xâu con có độ dài lớn hơn 2
    for k in range(3, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True

    # tạo ra danh sách các xâu đối xứng
    result = []
    for i in range(n):
        for j in range(i, n):
            if dp[i][j]:
                result.append(s[i:j + 1])
    return result

Hàm find_palindromes(s) nhận đầu vào là một xâu s và trả về danh sách các xâu con của xâu đó sao cho các xâu con đó đều là xâu đối xứng.

Thuật toán này sử dụng một mảng 2 chiều để lưu trữ kết quả. Đầu tiên, nó tìm xâu con độ dài 1 và 2 là xâu đối xứng. Sau đó, nó tìm các xâu con có độ dài lớn hơn 2 bằng cách kiểm tra các xâu con có nằm trong xâu đối xứng hay không. Cuối cùng, nó tạo ra danh sách các xâu đối xứng bằng cách duyệt qua mảng kết quả và lưu trữ các xâu đối xứng.

Ví dụ sử dụng:

s = "abbaabba"
print(find_palindromes(s))
# Output: ['a', 'b', 'bb', 'abba', 'baab', 'abbaabba']

Cài đặt thuật toán Quy hoạch động với C++

#include <iostream>
#include <vector>
using namespace std;

vector<string> find_palindromes(string s) {
    int n = s.length();
    // khởi tạo một mảng 2 chiều để lưu trữ kết quả
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    // tìm xâu con độ dài 1 là xâu đối xứng
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // tìm xâu con độ dài 2 có thể là xâu đối xứng
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
        }
    }

    // tìm các xâu con có độ dài lớn hơn 2
    for (int k = 3; k <= n; k++) {
        for (int i = 0; i < n - k + 1; i++) {
            int j = i + k - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
            }
        }
    }

    // tạo ra danh sách các xâu đối xứng
    vector<string> result;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (dp[i][j]) {
                result.push_back(s.substr(i, j - i + 1));
            }
        }
    }
    return result;
}

int main() {
    string s = "abbaabba";
    vector<string> palindromes = find_palindromes(s);
    for (int i = 0; i < palindromes.size(); i++) {
        cout << palindromes[i] << " ";
    }
    return 0;
}

Hàm find_palindromes(s) nhận đầu vào là một xâu s và trả về danh sách các xâu con của xâu đó sao cho các xâu con đó đều là xâu đối xứng.

Cài đặt thuật toán Sinh tổ hợp với Python

Để giải bài toán tách một xâu thành các xâu con đối xứng bằng thuật toán Sinh tổ hợp, ta có thể sử dụng các bước sau:

Với mỗi k trong khoảng từ 1 đến n, thực hiện sinh tổ hợp các chỉ số i1, i2, …, ik có giá trị trong khoảng từ 0 đến n-1. Đây là các chỉ số của các phần tử trong xâu con đối xứng cần tách ra.
Kiểm tra xem các chỉ số vừa sinh có tạo thành được các xâu con đối xứng không. Nếu có, thêm các xâu con này vào danh sách kết quả.

Dưới đây là một cách cài đặt thuật toán này bằng Python:

def is_palindrome(s):
    return s == s[::-1]

def generate_combinations(n, k):
    # Khởi tạo một danh sách với các giá trị đầu tiên của tổ hợp
    combo = [i for i in range(k)]

    while True:
        yield combo

        # Tìm chỉ số cuối cùng mà giá trị combo[i] không phải là giá trị cuối cùng có thể có
        i = k - 1
        while i >= 0 and combo[i] == n - k + i:
            i -= 1

        # Nếu không tìm thấy, thì đã sinh được tất cả các tổ hợp
        if i < 0:
            return

        # Tăng giá trị tại vị trí i lên 1
        combo[i] += 1

        # Đặt lại các giá trị sau vị trí i
        for j in range(i+1, k):
            combo[j] = combo[i] + j - i

def split_palindrome(s):
    n = len(s)
    results = []
    for k in range(1, n+1):
        for combo in generate_combinations(n, k):
            sub_strings = [s[combo[i]:combo[i+1]] for i in range(len(combo)-1)]
            if all(is_palindrome(sub_str) for sub_str in sub_strings):
                results.append(sub_strings)
    return results

s = "abcbab"
print(split_palindrome(s))

Cài đặt thuật toán Sinh tổ hợp với C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool is_palindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n-i-1]) {
            return false;
        }
    }
    return true;
}

void generate_combinations(int n, int k, vector<vector<int>>& combos) {
    vector<int> combo(k, 0);
    int i = 0;
    while (i >= 0) {
        combo[i]++;
        if (combo[i] > n) {
            i--;
        } else if (i == k-1) {
            combos.push_back(combo);
        } else {
            i++;
            combo[i] = combo[i-1];
        }
    }
}

vector<vector<string>> split_palindrome(string s) {
    int n = s.length();
    vector<vector<string>> results;

    for (int k = 1; k <= n; k++) {
        vector<vector<int>> combos;
        generate_combinations(n-1, k-1, combos);
        for (auto& combo : combos) {
            vector<string> sub_strings(k);
            for (int i = 0; i < k; i++) {
                sub_strings[i] = s.substr(combo[i], combo[i+1]-combo[i]);
            }
            if (all_of(sub_strings.begin(), sub_strings.end(), is_palindrome)) {
                results.push_back(sub_strings);
            }
        }
    }

    return results;
}

int main() {
    string s = "abcbab";
    vector<vector<string>> res = split_palindrome(s);
    for (auto& sub_strings : res) {
        for (auto& sub_str : sub_strings) {
            cout << sub_str << " ";
        }
        cout << endl;
    }
    return 0;
}

Hàm is_palindrome(s) kiểm tra xem một xâu s có phải là xâu đối xứng hay không.

Hàm generate_combinations(n, k, combos) sinh ra tất cả các tổ hợp có k phần tử từ tập n phần tử, và lưu kết quả vào biến combos dưới dạng một vector các vector chỉ số.

Hàm split_palindrome(s) tách xâu s thành các xâu con đối xứng bằng cách sinh ra tất cả các tổ hợp chỉ số của các phần tử trong các xâu con, và kiểm tra từng tổ hợp này xem có tạo thành được các xâu con đối xứng không.

Trong hàm main(), ta khởi tạo xâu s và gọi hàm split_palindrome(s) để tìm các xâu con đối xứng của s. Kết quả được lưu vào biến res và được in ra màn hình.

Cài đặt Giải thuật Manacher với C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> manacher(string s) {
    int n = s.length();
    vector<int> p(n);

    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        if (i < right) {
            p[i] = min(right-i, p[2*center-i]);
        }
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n && s[i-p[i]-1] == s[i+p[i]+1]) {
            p[i]++;
        }
        if (i+p[i] > right) {
            center = i;
            right = i+p[i];
        }
    }

    return p;
}

vector<vector<string>> split_palindrome(string s) {
    int n = s.length();
    vector<vector<string>> results;

    vector<int> p = manacher(s);
    for (int i = 0; i < n; i++) {
        int len = p[i];
        if (len == 0) {
            continue;
        }
        int start = i-len, end = i+len;
        if (start == 0 && end == n-1) {
            results.push_back({s});
        } else {
            vector<vector<string>> sub_results = split_palindrome(s.substr(0, start+1));
            for (auto& sub_result : sub_results) {
                sub_result.push_back(s.substr(start+1, len));
                results.push_back(sub_result);
            }
        }
    }

    return results;
}

int main() {
    string s = "abcbab";
    vector<vector<string>> res = split_palindrome(s);
    for (auto& sub_strings : res) {
        for (auto& sub_str : sub_strings) {
            cout << sub_str << " ";
        }
        cout << endl;
    }
    return 0;
}

Cài đặt Giải thuật Manacher với Python

def manacher(s):
    n = len(s)
    p = [0] * n
    center, right = 0, 0
    for i in range(n):
        if i < right:
            p[i] = min(right-i, p[2*center-i])
        while i-p[i]-1 >= 0 and i+p[i]+1 < n and s[i-p[i]-1] == s[i+p[i]+1]:
            p[i] += 1
        if i+p[i] > right:
            center, right = i, i+p[i]
    return p

def split_palindrome(s):
    n = len(s)
    results = []
    p = manacher(s)
    for i in range(n):
        length = p[i]
        if length == 0:
            continue
        start, end = i-length, i+length
        if start == 0 and end == n-1:
            results.append([s])
        else:
            sub_results = split_palindrome(s[:start+1])
            for sub_result in sub_results:
                sub_result.append(s[start+1:end])
                results.append(sub_result)
    return results

s = "abcbab"
res = split_palindrome(s)
for sub_strings in res:
    print(" ".join(sub_strings))

Hàm manacher(s) tính các bán kính của tất cả các đoạn con đối xứng của xâu s bằng giải thuật Manacher và trả về một danh sách p có độ dài bằng độ dài của xâu s. Giá trị p[i] chứa bán kính của đoạn con đối xứng tại vị trí i.

Hàm split_palindrome(s) tách xâu s thành các xâu con đối xứng bằng cách duyệt qua các vị trí trong xâu s và tìm các đoạn con đối xứng tại mỗi vị trí bằng cách sử dụng giải thuật Manacher. Nếu đoạn con đối xứng tại vị trí đó là toàn bộ xâu s, ta lưu xâu s vào kết quả. Ngược lại, ta gọi đệ quy để tách xâu s thành các xâu con đối xứng ở phần đầu của đoạn con đối xứng.

Đánh giá độ phức tạp của các thuật toán

Quy hoạch động:

Thời gian: O(n^2)
Không gian: O(n)

Sinh tổ hợp:

Thời gian: O(2^n)
Không gian: O(n)

Giải thuật Manacher:

Thời gian: O(n)
Không gian: O(n)

Tuy nhiên, trong thực tế, các thuật toán này có thể được cải tiến để có hiệu suất tốt hơn. Ví dụ, quy hoạch động có thể được cải tiến bằng cách sử dụng kỹ thuật truy hồi đuôi để giảm độ phức tạp xuống O(n) hoặc sử dụng kỹ thuật quy hoạch động hai chiều để giảm độ phức tạp xuống O(n^2/log(n))). Các cải tiến như vậy cũng được áp dụng cho sinh tổ hợp để giảm độ phức tạp.

Kết Luận

Bài toán tách một xâu ra thành các xâu con đối xứng là một bài toán thường gặp trong lĩnh vực xử lý ngôn ngữ tự nhiên, xử lý chuỗi. Trong bài viết này, chúng ta đã giới thiệu ba thuật toán để giải quyết bài toán này là quy hoạch động, sinh tổ hợp và giải thuật Manacher.

Thuật toán quy hoạch động là phương pháp giải quyết bài toán bằng cách chia bài toán thành các bài toán con nhỏ hơn và lưu trữ các kết quả tính toán để sử dụng lại sau này. Tuy nhiên, độ phức tạp của thuật toán quy hoạch động là khá lớn, nên không phải là giải pháp tốt nhất cho bài toán này.

Thuật toán sinh tổ hợp giải quyết bài toán bằng cách sinh ra tất cả các tổ hợp của chuỗi ban đầu và kiểm tra xem chúng có phải là các chuỗi đối xứng hay không. Tuy nhiên, độ phức tạp của thuật toán này là rất cao, do đó chỉ nên sử dụng khi số lượng chuỗi con của chuỗi ban đầu là nhỏ.

Giải thuật Manacher là phương pháp giải quyết bài toán bằng cách tận dụng các thông tin về chuỗi đối xứng để giảm độ phức tạp của thuật toán xuống O(n). Đây là giải pháp hiệu quả nhất và nên được sử dụng trong thực tế.

Tóm lại, giải thuật Manacher là giải pháp tốt nhất cho bài toán tách một xâu ra thành các xâu con đối xứng, do có độ phức tạp thấp và hiệu quả trong thực tế. Tuy nhiên, cả quy hoạch động và sinh tổ hợp đều có thể được cải tiến để có hiệu suất tốt hơn, tùy thuộc vào mục đích sử dụng và quy mô bài toán cụ thể./.

Lập trình C/C++, Lập trình Pascal