在 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

Ayush Gupta

更新於：2020-02-17

141 次瀏覽

開始您的 職業生涯

完成課程並獲得證書

立即開始