เราได้รับสตริง str เป้าหมายคือการนับสตริงย่อยทั้งหมดของ str ที่เป็น palindromes พิเศษและมีความยาวมากกว่า 1 palindromes พิเศษคือสตริงที่มีอักขระเดียวกันทั้งหมดหรือเฉพาะอักขระตรงกลางเท่านั้นที่ต่างกัน ตัวอย่างเช่น หากสตริงคือ “baabaa” ดังนั้น palindromes พิเศษที่เป็นสตริงย่อยของต้นฉบับคือ “aa”, “aabaa”, “aba”, “aa”
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − str=”abccdcdf”
ผลผลิต − จำนวนพาลินโดรมพิเศษในสตริงคือ − 3
คำอธิบาย − สตริงย่อยที่เป็นพาลินโดรมพิเศษคือ − “cc”, “cdc”, “dcd”
ป้อนข้อมูล − str=”baabaab”
ผลผลิต − จำนวนพาลินโดรมพิเศษในสตริงคือ − 4
คำอธิบาย − สตริงย่อยที่เป็นพาลินโดรมพิเศษคือ − “aa”, “aabaa”, “aba”, “aa”
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
สร้างชุดตัวอักษรและคำนวณความยาว ส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป
-
ประกาศตัวแปรชั่วคราว นับ และฉัน และตั้งค่าให้เป็น 0
-
สร้างอาร์เรย์ของขนาดของสตริงและเริ่มต้นด้วย 0
-
เริ่ม WHILE จนถึง i น้อยกว่าความยาวของสตริง
-
ภายใน while ให้ตั้งค่าตัวแปรเป็นผลรวมเป็น 1 และตัวแปร j เป็น i + 1
-
เริ่มอีกในขณะที่ str[i] =str[j] และ j น้อยกว่าความยาวของสตริง
-
ในระหว่างนี้ ให้เพิ่มผลรวม 1 และ j ขึ้น 1
-
ตั้งค่าการนับเป็นจำนวน + ( ทั้งหมด * (รวม + 1) / 2, arr[i] เป็นยอดทั้งหมด และ i เป็น j
-
เริ่มวนซ้ำ FOR จาก j ถึง 1 จนถึงความยาวของสตริง
-
ตรวจสอบว่า str[j] =str[j-1] แล้วตั้งค่า arr[j] เป็น arr[j-1]
-
ตั้งค่าตัวแปร temp เป็น str[j-1] และตรวจสอบว่า j> 0 AND j <น้อยกว่าความยาวของสตริงหรือไม่ AND temp =str[j+1] AND sr[j]!=temp จากนั้นให้นับเป็น count + มิน(arr[j-1], arr[j+1])
-
ตั้งค่าการนับ นับ - ความยาวของสตริง
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len){
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len){
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++){
if (str[j] == str[j - 1]){
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main(){
string str = "bcbaba";
int len = str.length();
cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of special palindromes in a String are: 3
