Đếm chuỗi con palindrome trong khoảng chỉ số trong C++

Cho một chuỗi và một khoảng từ start đến end. Nhiệm vụ: đếm số chuỗi con palindrome trong khoảng chỉ số cho trước. Chuỗi palindrome là chuỗi đọc xuôi ngược giống nhau như "nitin", "aba".

Ví dụ

Đầu vào: InputString = "cccaabbbdee", start = 2, end = 6

Đầu ra: Số chuỗi con palindrome trong khoảng: 7

Giải thích: Duyệt từ chỉ số 2 ('c') đến 6 ('b') → chuỗi con "caabb". Các chuỗi con palindrome: 'c', 'a', 'a', 'b', 'b', 'aa', 'bb' → 7.

Đầu vào: InputString = "lioaabbbdee", start = 0, end = 2

Đầu ra: Số chuỗi con palindrome trong khoảng: 3

Giải thích: Chuỗi con "lio". Palindrome: 'l', 'i', 'o' → 3.

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

• Khai báo chuỗi và khoảng start, end.
• Truyền vào hàm palindrome_index(arr, InputString).
• Khai báo mảng checked kích thước mảng.
• Vòng lặp FOR i 0 đến độ dài, FOR j 0 đến độ dài: check[i][j] = 0, arr[i][j] = 0.
• Vòng lặp FOR i từ length-1 xuống 0: check[i][i] = arr[i][i] = 1.
• Vòng lặp FOR j từ i+1 đến độ dài:
  • Nếu s[i] == s[j] và (i+1 > j-1 hoặc check[i+1][j-1] != 0) → check[i][j] = 1.
  • Ngược lại check[i][j] = 0.
  • arr[i][j] = arr[i][j-1] + arr[i+1][j] - arr[i+1][j-1] + check[i][j].
• In arr[start][end].

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

import java.io.*; 

class testqwe { 
    static void palindrome_index(int arr[][], String s) { 
        int length = s.length(); 
        int[][] check = new int[length + 1][length + 1]; 
        for (int i = 0; i <= length; i++) { 
            for (int j = 0; j <= length; j++) { 
                check[i][j] = 0; 
                arr[i][j] = 0; 
            } 
        } 
        for (int i = length - 1; i >= 0; i--) { 
            check[i][i] = arr[i][i] = 1; 
            for (int j = i + 1; j < length; j++) { 
                if (s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || check[i + 1][j - 1] != 0)) { 
                    check[i][j] = 1; 
                } else { 
                    check[i][j] = 0; 
                } 
                arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j]; 
            } 
        } 
    } 
    public static void main(String args[]) { 
        String InputString = "cccaabbbdee"; 
        int[][] arr = new int[50][50]; 
        palindrome_index(arr, InputString); 
        int start = 2; 
        int end = 6; 
        System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]); 
    } 
}

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

Kết quả

Count of Palindromic substrings in an Index range 7