จำนวนซับสตริงอะนาครัมทั้งหมดใน C++

เราได้รับสตริง str[] เป็นอินพุต เป้าหมายคือนับจำนวนซับสตริงอะนาครัมที่มีอยู่ใน str[] สองสตริงเป็นอะนาครัมของกันและกันถ้าพวกเขามีจำนวนตัวอักษรเท่ากันและตัวอักษรทุกตัวปรากฏในทั้งสอง ลำดับของตัวอักษรอาจต่างกัน

"abc" เป็นอะนาครัมของ "cba", "bca" ฯลฯ

ตัวอย่าง

อินพุต - str[] = "abccb"

เอาต์พุต - จำนวนซับสตริงอะนาครัมทั้งหมดคือ - 4

คำอธิบาย - อะนาครัมคือ - (b,b), (c,c), (bc,cb), (bcc,ccb)

อินพุต - str = "aaa"

เอาต์พุต - จำนวนซับสตริงอะนาครัมทั้งหมดคือ - 4

คำอธิบาย - อะนาครัมคือ - (a,a), (a,a), (a,a), (aa,aa)

แนวทางที่ใช้ในโปรแกรมด้านล่าง

เราใช้ map ที่มี vector ที่มีความถี่ของตัวอักษรภาษาอังกฤษในซับสตริงและจำนวนซับสตริงแบบนั้นในอาร์เรย์ ใน map<vector<int>, int> mp_vec; vector<int> vec(MAX, 0) จะเก็บความถี่ของตัวอักษร 26 ตัวในซับสตริงปัจจุบัน และจำนวนเต็มที่ map ไปจะเป็นจำนวนซับสตริงที่มีเวกเตอร์ความถี่เดียวกัน สำหรับแต่ละซับสตริงถ้าจำนวนเป็น x สำหรับอะนาครัม แล้วคู่อะนาครัมทั้งหมดจะเป็น x*(x-1)/2

• รับสตริง str[] เป็นอาร์เรย์ตัวอักษร
• ฟังก์ชัน anagram_substring(string str, int length) รับสตริงและคืนค่าจำนวนซับสตริงอะนาครัมทั้งหมด
• ตั้งค่า count เริ่มต้นเป็น 0
• ใช้ map, map<vector<int>, int> mp_vec
• เดินทางผ่าน str[] โดยใช้ลูป for สองอันจาก i=0 ถึง i
• สำหรับซับสตริง str[i ถึง j] vector<int> vec(MAX, 0) จะมีจำนวนตัวอักษรภาษาอังกฤษในมัน
• รับตัวอักษรปัจจุบันใน c เป็น str[j] รับค่าจำนวนเต็มของมันโดย temp=c-'a'
• อัปเดตความถี่ด้วย vec[temp]++
• เพิ่มจำนวนที่สอดคล้องกับเวกเตอร์ความถี่นี้โดย mp_vec[vec]++
• ตอนนี้เดินทางผ่าน map ที่มีเวกเตอร์ความถี่ทั้งหมดและรวมจำนวนซับสตริงโดยใช้ลูป for จาก iterator it=mp_vec.begin() ถึง it != mp_vec.end()
• สำหรับแต่ละจำนวนเป็น it->second บวก ((last) * (last-1))/2 เข้า count สำหรับคู่อะนาครัมทั้งหมด
• ที่สิ้นสุด เราจะมีจำนวนอะนาครัมทั้งหมด
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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; isecond; 
        count += ((last) * (last-1))/2; 
    } 
    return count; 
} 

int main(){ 
    string str = "TP"; 
    int length = str.length(); 
    cout << "Count of total anagram substrings are: " << anagram_substring(str, length) << endl; 
    return 0; 
}

เอาต์พุต

Count of total anagram substrings are: 3