C++ですべてのプライムレングスのパリンドローム部分文字列をカウントします

このチュートリアルでは、素数のパリンドローム文字列の数を見つけるプログラムについて説明します。

このために、文字列が提供されます。私たちのタスクは、パリンドロームでプライムレングスのすべてのサブストリングをカウントすることです。

例

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

出力

3