Đếm xâu đối xứng đặc biệt trong chuỗi trong C++

Cho một chuỗi str. Mục tiêu là đếm tất cả các chuỗi con của str là xâu đối xứng đặc biệt (special palindromes) và có độ dài lớn hơn 1. Xâu đối xứng đặc biệt là chuỗi mà hoặc tất cả ký tự đều giống nhau, hoặc chỉ ký tự giữa khác (ví dụ: "aa", "aabaa", "aba").

Ví dụ

Đầu vào: str = "abccdcdf"
Đầu ra: 3
Giải thích: Các chuỗi con: "cc", "cdc", "dcd".

Đầu vào: str = "baabaab"
Đầu ra: 4
Giải thích: "aa", "aabaa", "aba", "aa".

Giải thuật

• Tạo mảng arr kích thước độ dài chuỗi, khởi tạo 0.
• Duyệt chuỗi, nhóm các ký tự liên tiếp giống nhau, tính số chuỗi con toàn ký tự giống nhau: total * (total + 1) / 2.
• Duyệt lần 2 để xử lý trường hợp ký tự giữa khác: nếu str[j] == str[j-1] thì arr[j] = arr[j-1]. Nếu str[j-1] == str[j+1] và str[j] != str[j-1] thì cộng thêm min(arr[j-1], arr[j+1]).
• Trừ đi độ dài chuỗi (loại bỏ các chuỗi con độ dài 1).

Ví dụ triển khai

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

int count_palindromes(string str, int len) {
    int count = 0, i = 0;
    int arr[len] = {0};
    while (i < len) {
        int total = 1;
        int j = i + 1;
        while (str[i] == str[j] && j < len) {
            total++;
            j++;
        }
        count += (total * (total + 1) / 2);
        arr[i] = total;
        i = j;
    }
    for (int j = 1; j < len; j++) {
        if (str[j] == str[j - 1]) {
            arr[j] = arr[j - 1];
        }
        char temp = str[j - 1];
        if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)) {
            count += min(arr[j-1], arr[j+1]);
        }
    }
    count = count - len;
    return count;
}

int main() {
    string str = "bcbaba";
    int len = str.length();
    cout << "Count of special palindromes in a String are: " << count_palindromes(str, len);
    return 0;
}

Kết quả

Count of special palindromes in a String are: 3