Đếm các palindromes đặc biệt trong một chuỗi trong C ++

Chúng tôi được cung cấp một chuỗi str. Mục đích là đếm tất cả các chuỗi con của str là các palindrom đặc biệt và có độ dài lớn hơn 1. Các palindromes đặc biệt là các chuỗi có tất cả các ký tự giống nhau hoặc chỉ có ký tự giữa là khác nhau. Ví dụ:nếu chuỗi là “baabaa” thì các palindromes đặc biệt là chuỗi con của chuỗi gốc là “aa”, “aabaa”, “aba”, “aa”

Hãy cho chúng tôi hiểu với các ví dụ.

Đầu vào - str =”abccdcdf”

Đầu ra - Số lượng palindromes đặc biệt trong một chuỗi là - 3

Giải thích - Các chuỗi con là palindromes đặc biệt là - “cc”, “cdc”, “dcd”

Đầu vào - str =”baabaab”

Đầu ra - Số lượng palindromes đặc biệt trong một chuỗi là - 4

Giải thích - Các chuỗi con là palindromes đặc biệt là - “aa”, “aabaa”, “aba”, “aa”

Cách tiếp cận được sử dụng trong chương trình dưới đây như sau

• Tạo một chuỗi bảng chữ cái và tính độ dài của nó. Chuyển dữ liệu đến hàm để xử lý thêm.

• Khai báo số lượng biến tạm thời và i và đặt chúng thành 0

• Tạo một mảng có kích thước của một chuỗi và khởi tạo nó bằng 0.

• Bắt đầu WHILE cho đến khi tôi nhỏ hơn độ dài của một chuỗi

• Bên trong while, đặt một biến là tổng thành 1 và biến j thành i + 1

• Bắt đầu một WHILE khác cho đến khi str [i] =str [j] VÀ j nhỏ hơn độ dài của một chuỗi

• Trong khi đó, tăng tổng số 1 và j lên 1

• Đặt số đếm là count + (tổng * (tổng + 1) / 2, arr [i] thành tổng và i thành j

• Bắt đầu vòng lặp FOR từ j đến 1 cho đến hết độ dài của một chuỗi

• Kiểm tra xem str [j] =str [j-1] rồi đặt arr [j] thành arr [j-1]

• Đặt một biến nhiệt độ thành str [j-1] và kiểm tra xem j> 0 VÀ j

• Đặt số đếm là số đếm - độ dài của một chuỗi

• Trả lại số lượng

• In kết quả.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of special palindromes in a String are: 3