在 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

更新于:2020-02-17

141 次浏览

开始您的 职业生涯

完成课程并获得证书

立即开始
广告