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

• ใช้สตริง str[] เป็นอาร์เรย์อักขระ

• ฟังก์ชัน anagram_substring(string str, int length) รับสตริงและส่งกลับจำนวนสตริงย่อยแอนนาแกรมทั้งหมด

• นับเริ่มต้นเป็น 0

• นำแผนที่ map, int> mp_vec;

• ข้าม str[] โดยใช้สองลูปจาก i=0 ถึง i

• สำหรับแต่ละสตริงย่อย str[i ถึง j] เวกเตอร์ vec(MAX, 0); จะมีตัวอักษรภาษาอังกฤษอยู่ในนั้น

• ใช้อักขระปัจจุบันใน c เป็น str[j] ใช้ค่าจำนวนเต็มโดย temp=c-’a’

• อัปเดตความถี่โดย vec[ชั่วคราว]++

• เพิ่มจำนวนที่สอดคล้องกับเวกเตอร์ความถี่นี้โดยใช้ mp_vec[vec]++

• ตอนนี้สำรวจแผนที่ที่มีเวกเตอร์ความถี่ทั้งหมดและจำนวนสตริงย่อยรวมโดยใช้ลูปจาก iterator it=mp_vec.begin() ถึงมัน !=mp_vec.end()

• สำหรับแต่ละอันนับเป็น it->วินาที ให้เพิ่ม ((last) * (last-1))/2 เพื่อนับสำหรับแอนนาแกรมทุกคู่

• ในตอนท้ายเราจะนับแอนนาแกรมทั้งหมด

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of total anagram substrings are: 3