นับซับสตริงพาลินโดรมที่มีความยาวเป็นจำนวนเฉพาะใน 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