เราได้รับอินพุตเป็นสตริง ภารกิจคือการค้นหาจำนวนคู่ของสตริงย่อย palindromic ที่ไม่ทับซ้อนกันของสตริงอินพุตที่กำหนด ค่าของ arr[i][j] เป็นจริงหากสตริงย่อยเป็น palindrome มิฉะนั้นจะเป็นเท็จ เราจะนำชุดค่าผสมออกจากสตริงและตรวจสอบว่าคู่ตรงตามเกณฑ์หรือไม่
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล: เอบีซี
ผลลัพธ์: นับคู่ของสตริงย่อยพาลินโดรมที่ไม่ทับซ้อนกันคือ 3
คำอธิบาย: คู่ที่เป็นไปได้คือ (A) (B) (C) ,(A) (BC),(AB) (C),(ABC)
ป้อนข้อมูล: ABCD
ผลลัพธ์: นับคู่ของสตริงย่อยพาลินโดรมที่ไม่ทับซ้อนกันคือ 8
คำอธิบาย: คู่ที่เป็นไปได้คือ (A)(B)(C)(D),(A)(B)(CD),(A)(BC)(D),(A)(BCD),(AB)(C) (D),(AB)(ซีดี),
(ABC)(D),(ABCD)
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- สตริงถูกใช้เป็นอินพุตและส่งผ่านในฟังก์ชัน pair_count(text) เพื่อการประมวลผลต่อไป
- เริ่มแรกอาร์เรย์ 2 มิติบูลีนขนาด 100 arr[ ][ ] ถูกสร้างและดูแลให้เติมด้วยวิธีจากล่างขึ้นบน และสตริงอินพุต (ข้อความ) จะถูกแปลงเป็นอาร์เรย์อักขระ
- อาร์เรย์จะคำนวณโดยการตรวจสอบค่า arr[i+1][j-1] หากค่าเป็นจริงและ str[i] เหมือนกับ str[j] เราก็สร้าง arr[i] [j] จริง. มิฉะนั้น ค่าของ arr[i][j] จะเป็นเท็จ
- หลังจากนั้น start[ ] และ end[ ] จะถูกเตรียมข้อมูลเบื้องต้นและ start[i] จะเก็บจำนวน palindrome ของจำนวน palindrome ทางด้านซ้ายของดัชนี (รวมถึง i) และ end[i] เก็บจำนวน palindrome ของตัวเลข ขององค์ประกอบทางด้านขวาของดัชนี (รวมถึง i)
- จากนั้นวนซ้ำจาก 0 ถึง str.length() - 1 และภายในลูป ผลลัพธ์จะถูกคำนวณโดยการสรุปผลลัพธ์ด้วยผลคูณของ start[i] * end[i + 1]
ตัวอย่าง
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));
}
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count pairs of non-overlapping palindromic sub-strings is 8
