Đếm tất cả xâu con palindrome có độ dài nguyên tố trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng xâu con (substring) palindrome có độ dài là số nguyên tố.

Cho một xâu. Nhiệm vụ là đếm tất cả các xâu con là palindrome và có độ dài nguyên tố.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

bool if_palin(string str, int i, int j) {
    while(i < j) {
        if(str[i] != str[j]) return false;
        i++; j--;
    }
    return true;
}

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

Kết quả

3