Đếm tất cả các chuỗi con Palindromic có độ dài cơ bản trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số lượng các chuỗi palindromic có độ dài nguyên tố.

Đối với điều này, chúng tôi sẽ được cung cấp một chuỗi. Nhiệm vụ của chúng ta là đếm tất cả các chuỗi con là palindromes và có độ dài nguyên tố.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//checking for a palindrome
bool if_palin(string str, int i, int j){
   while (i < j) {
      if (str[i] != str[j])
         return false;
      i++;
      j--;
   }
   return true;
}
//counting palindrome with prime length
int count_prime(string str, int len){
   bool prime[len + 1];
   memset(prime, true, sizeof(prime));
   prime[0] = prime[1] = false;
   for (int p = 2; p * p <= len; p++) {
      if (prime[p]) {
         for (int i = p * p; i <= len; i += p)
            prime[i] = false;
      }
   }
   int count = 0;
   for (int j = 2; j <= len; j++) {
      if (prime[j]) {
         for (int i = 0; i + j - 1 < len; i++) {
            if (if_palin(str, i, i + j - 1))
               count++;
         }
      }
   }
   return count;
}
int main(){
   string s = "abccc";
   int len = s.length();
   cout << count_prime(s, len);
   return 0;
}

Đầu ra

3