เราได้รับสตริงและช่วงที่เริ่มต้นตั้งแต่ต้นจนจบ และภารกิจคือการคำนวณจำนวนสตริงย่อย palindromic ที่มีอยู่ในช่วงที่กำหนด สตริง Palindrome เป็นสตริงที่คล้ายคลึงกันจากไปข้างหน้าและข้างหลังของสตริงเช่น nitin, aba เป็นต้น
ตัวอย่าง
อินพุต - InputString ="cccaabbbdee", start =2, end =6;
ผลลัพธ์ - จำนวนสตริงย่อย Palindromic ในช่วงดัชนี 7
คำอธิบาย - เราได้รับช่วงและสตริงดังนั้นเราจะเริ่มสำรวจสตริงจากตัวชี้เริ่มต้นซึ่งเป็น 2 นั่นคือ 'c' ถึง 6 i.e. 'b' ดังนั้นสตริงย่อยจึงเป็น 'caabb' ดังนั้นสตริงย่อยพาลินโดรมคือ 'c', 'a', 'a', 'b' , 'b', 'aa' และ 'bb' ดังนั้น การนับสตริงย่อยพาลินโดรมคือ 7
อินพุต - InputString ="lioaabbbdee", start =0, end =2;
ผลลัพธ์ - จำนวนสตริงย่อย Palindromic ในช่วงดัชนี 3
คำอธิบาย - เราได้รับช่วงและสตริงดังนั้นเราจะเริ่มสำรวจสตริงจากตัวชี้เริ่มต้นซึ่งเป็น 0 นั่นคือ 'l' ถึง 2 คือ 'o' ดังนั้นสตริงย่อยจึงเป็น 'lio' ดังนั้นสตริงย่อยพาลินโดรมคือ 'l', 'i' และ 'o' ดังนั้น การนับสตริงย่อยพาลินโดรมคือ 3
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- ประกาศสตริงของขนาดที่กำหนดและช่วงที่เริ่มต้นจากตัวแปรตั้งแต่ต้นจนจบ
- ส่งข้อมูลไปยังฟังก์ชันชื่อ palindrome_index(arr, InputString) สำหรับการประมวลผลต่อไป
- ภายในฟังก์ชัน ให้ประกาศอาร์เรย์อื่นที่มีชื่อตรวจสอบด้วยขนาดอาร์เรย์
- เริ่มลูป FOR i ตั้งแต่ 0 จนถึงความยาวของอาร์เรย์
- ภายในลูป ให้เริ่มวนซ้ำสำหรับ j จาก 0 จนถึงความยาวของอาร์เรย์
- ภายในลูป ตั้งค่า check as check[i][j] =0 and arr[i][j] =0
- เริ่มลูป FOR i จากความยาว - 1 ถึง i มากกว่า 0
- ภายในลูป ตั้งค่า check และ arr ของ i เป็น 1 จากนั้นเริ่มลูปอื่น FOR j จาก i + 1 จนถึงความยาวของอาร์เรย์
- ภายในลูป ตรวจสอบว่า IF string ที่ i i เท่ากับ string ที่ j และ i + 1 มากกว่า j - 1 OR 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] + ตรวจสอบ[i][j]
- พิมพ์อาร์เรย์ 2 มิติเป็นจุดเริ่มต้นและจุดสิ้นสุด
ตัวอย่าง
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;
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]);
}
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of Palindromic substrings in an Index range 7
