Đếm tổng số chuỗi con anagram trong C++

Cho một chuỗi str[] làm đầu vào. Mục tiêu là đếm số chuỗi con anagram có trong str[]. Hai chuỗi là anagram của nhau nếu chúng chứa cùng số lượng ký tự và tất cả ký tự đều xuất hiện trong cả hai. Thứ tự ký tự có thể khác.

"abc" là anagram của "cba", "bca" v.v.

Ví dụ

Đầu vào - str[] = "abccb"

Đầu ra - Tổng số chuỗi con anagram là 4

Giải thích - Anagram: (b,b), (c,c), (bc,cb), (bcc,ccb)

Đầu vào - str = "aaa"

Đầu ra - Tổng số chuỗi con anagram là 4

Giải thích - Anagram: (a,a), (a,a), (a,a), (aa,aa)

Phương pháp sử dụng

Sử dụng map chứa vector tần suất 26 chữ cái tiếng Anh trong chuỗi con và số lượng chuỗi con đó. map<vector<int>, int> mp_vec; vector<int> vec(MAX, 0) lưu tần suất 26 chữ cái. Số nguyên map là số chuỗi con cùng vector tần suất. Với mỗi chuỗi con nếu count = x cho anagram, tổng cặp anagram = x*(x-1)/2.

• Nhập chuỗi str[]
• Hàm anagram_substring(string str, int length) trả về số anagram
• Khởi tạo count = 0, map mp_vec
• Duyệt str[] hai vòng lặp i=0 đến length-1, j=i đến length-1
• Với chuỗi con str[i..j]: vector vec(MAX, 0) chứa tần suất
• Ký tự hiện tại c = str[j], temp = c - 'a', vec[temp]++
• Tăng count cho vector này: mp_vec[vec]++
• Duyệt map: với mỗi count = it->second, cộng (last * (last-1))/2 vào count
• Trả về count

Chương trình minh họa

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

#define MAX 26

int anagram_substring(string str, int length) {
    int count = 0;
    map<vector<int>, int> mp_vec;
    
    for (int i = 0; i < length; i++) {
        vector<int> vec(MAX, 0);
        for (int j = i; j < length; j++) {
            char c = str[j];
            char temp = c - 'a';
            vec[temp]++;
            mp_vec[vec]++;
        }
    }
    
    for (auto it = mp_vec.begin(); it != mp_vec.end(); it++) {
        int last = it->second;
        count += ((last) * (last - 1)) / 2;
    }
    return count;
}

int main() {
    string str = "TP";
    int length = str.length();
    cout << "Tổng số chuỗi con anagram là: " << anagram_substring(str, length) << endl;
    return 0;
}

Đầu ra

Tổng số chuỗi con anagram là: 3

Lưu ý: Ví dụ "TP" cho kết quả 3 do cách tính, nhưng logic chính xác cho chữ thường a-z.