Đếm cặp chuỗi con palindrome không chồng lấn trong C++

Cho một chuỗi đầu vào, nhiệm vụ là tìm số cặp chuỗi con palindrome không chồng lấn. Giá trị arr[i][j] là true nếu chuỗi con là palindrome, ngược lại false. Chúng ta lấy tổ hợp từ chuỗi và kiểm tra các cặp có thỏa mãn tiêu chí.

Hiểu qua ví dụ

Đầu vào: ABC

Đầu ra: Số cặp chuỗi con palindrome không chồng lấn là 3

Giải thích: Các cặp có thể: (A)(B)(C), (A)(BC), (AB)(C), (ABC)

Đầu vào: ABCD

Đầu ra: Số cặp chuỗi con palindrome không chồng lấn là 8

Giải thích: Các cặp: (A)(B)(C)(D), (A)(B)(CD), (A)(BC)(D), (A)(BCD), (AB)(C)(D), (AB)(CD), (ABC)(D), (ABCD)

Phương pháp sử dụng

• Nhập chuỗi, truyền vào hàm pair_count(text).
• Tạo mảng boolean 2D kích thước 100 arr[][] điền theo phương pháp bottom-up, chuyển chuỗi thành mảng ký tự.
• Tính mảng: nếu arr[i+1][j-1] true và str[i] == str[j] thì arr[i][j] = true, ngược lại false.
• Khởi tạo mảng start[] và end[]: start[i] lưu số palindrome bên trái chỉ số i (kể cả i), end[i] lưu số palindrome bên phải chỉ số i (kể cả i).
• Duyệt từ 0 đến str.length() - 1, cộng dồn result += start[i] * end[i + 1].

Ví dụ mã nguồn (Java)

import java.io.*; 
import java.util.*; 

class tutorialPoint { 
    static int SIZE = 100; 
    static int pair_count(String str) { 
        boolean arr[][] = new boolean[SIZE][SIZE]; 
        char[] ch = str.toCharArray(); 
        for (int i = 0; i < ch.length; i++) { 
            for (int j = 0; j < ch.length; j++) { 
                arr[i][j] = false; 
            } 
        } 
        for (int j = 1; j <= ch.length; j++) { 
            for (int i = 0; i <= ch.length - j; i++) { 
                if (j <= 2) { 
                    if (ch[i] == ch[i + j - 1]) { 
                        arr[i][i + j - 1] = true; 
                    } 
                } else if (ch[i] == ch[i + j - 1]) { 
                    arr[i][i + j - 1] = arr[i + 1][i + j - 2]; 
                } 
            } 
        } 
        int start[] = new int[str.length()]; 
        int end[] = new int[str.length()]; 
        start[0] = 1; 
        for (int i = 1; i < str.length(); i++) { 
            for (int j = 0; j <= i; j++) { 
                if (arr[j][i] == true) start[i]++; 
            } 
        } 
        end[str.length() - 1] = 1; 
        for (int i = str.length() - 2; i >= 0; i--) { 
            end[i] = end[i + 1]; 
            for (int j = str.length() - 1; j >= i; j--) { 
                if (arr[i][j] == true) end[i]++; 
            } 
        } 
        int result = 0; 
        for (int i = 0; i < str.length() - 1; i++) { 
            result = result + start[i] * end[i + 1]; 
        } 
        return result; 
    } 
    public static void main(String[] args) { 
        Scanner scan = new Scanner(System.in); 
        String text = scan.next(); 
        System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text)); 
    } 
}

Chạy mã trên cho kết quả:

Kết quả

Count pairs of non-overlapping palindromic sub-strings is 8