在 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
广告