Chúng ta được cấp một đầu vào là một chuỗi, nhiệm vụ là tìm ra số lượng các cặp chuỗi con palindromic không trùng nhau của chuỗi đầu vào đã cho. Giá trị của arr [i] [j] là true nếu chuỗi con là palindrome, ngược lại là false. Chúng tôi sẽ lấy kết hợp ra khỏi chuỗi và kiểm tra xem các cặp có đáp ứng tiêu chí hay không.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào: ABC
Đầu ra: Đếm số cặp chuỗi con palindromic không chồng chéo là 3
Giải thích: Các cặp có thể là (A) (B) (C), (A) (BC), (AB) (C), (ABC)
Đầu vào: ABCD
Đầu ra: Đếm số cặp chuỗi con palindromic không chồng chéo là 8
Giải thích: Các cặp có thể có là (A) (B) (C) (D), (A) (B) (CD), (A) (BC) (D), (A) (BCD), (AB) (C) (D), (AB) (CD),
(ABC) (D), (ABCD)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
- Một chuỗi được lấy làm đầu vào và được chuyển vào hàm pair_count (văn bản) để xử lý thêm.
- Ban đầu, một mảng 2D boolean có kích thước 100 arr [] [] được tạo và duy trì để được lấp đầy theo cách tiếp cận từ dưới lên và chuỗi đầu vào (văn bản) được chuyển đổi thành một mảng ký tự.
- Mảng sau đó được tính bằng cách kiểm tra giá trị arr [i + 1] [j-1], nếu giá trị là true và str [i] giống với str [j], thì chúng ta tạo arr [i] [j] đúng. Nếu không, giá trị của arr [i] [j] bị sai.
- Sau đó start [] và end [] được khởi tạo và start [i] lưu trữ số palindrome của số palindromes ở bên trái chỉ mục (bao gồm cả i) và end [i] lưu trữ số palindrome của số trong số các phần tử ở bên phải chỉ mục (bao gồm cả i)
- Sau đó, một vòng lặp được lặp lại từ 0 đến str.length () - 1 và bên trong vòng lặp, kết quả được tính bằng cách cộng kết quả với tích của start [i] * end [i + 1].
Ví dụ
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); //ABCD
String text = scan.next();
System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
}
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count pairs of non-overlapping palindromic sub-strings is 8