Tổng số chuỗi con đảo chữ trong C ++

Chúng tôi được cung cấp một chuỗi str [] làm đầu vào. Mục đích là để đếm số lượng chuỗi con đảo chữ có trong str []. Hai chuỗi là đảo ngữ của nhau nếu chúng chứa cùng một số ký tự và tất cả các ký tự đều xảy ra ở cả hai. Thứ tự của các ký tự có thể khác nhau.

“Abc” là đảo ngữ của “cba”, “bca”, v.v.

Hãy cho chúng tôi hiểu với các ví dụ.

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

Đầu ra - Tổng số chuỗi con đảo chữ cái là - 4

Giải thích - Đảo ngữ là - (b, b), (c, c), (bc, cb), (bcc, ccb)

Đầu vào - str =“aaa”

Đầu ra - Tổng số chuỗi con đảo chữ cái là - 4

Giải thích - Đảo ngữ là - (a, a), (a, a), (a, a), (aa, aa)

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng tôi đang lấy một bản đồ chứa các vectơ có tần số của bảng chữ cái tiếng Anh trong chuỗi con và số lượng các chuỗi con như vậy trong mảng. Trong bản đồ , int> mp_vec; vector vec (MAX, 0) sẽ lưu trữ tần số của tất cả 26 bảng chữ cái trong chuỗi con hiện tại. Và các số nguyên được ánh xạ sẽ được đếm các chuỗi con như vậy với cùng một vectơ tần số. Đối với mỗi chuỗi con nếu số đếm là x để đảo chữ cái. Khi đó, tổng các cặp đảo chữ cái sẽ là x * (x-1) / 2.

Lấy chuỗi str [] dưới dạng một mảng ký tự.
Hàm anagram_substring (string str, int length) nhận chuỗi và trả về tổng số chuỗi con đảo chữ.
Lấy số lượng ban đầu là 0.
Chụp bản đồ, bản đồ , int> mp_vec;
Đảo ngược str [] bằng cách sử dụng hai vòng lặp for từ i =0 đến i
Đối với mỗi chuỗi con str [i đến j]. vectơ vec (MAX, 0); sẽ chứa số lượng bảng chữ cái tiếng Anh trong đó.
Lấy ký tự hiện tại trong c là str [j]. Lấy giá trị nguyên của nó theo temp =c-’a ’.
Cập nhật tần suất bằng vec [temp] ++.
Tăng số lượng tương ứng với vectơ tần số này bằng cách sử dụng mp_vec [vec] ++.
Bây giờ, bản đồ đi ngang chứa tất cả vectơ tần số và tổng số chuỗi con bằng cách sử dụng vòng lặp for từ trình lặp it =mp_vec.begin () đến nó! =Mp_vec.end ().
Đối với mỗi số đếm là nó-> giây, hãy thêm ((cuối cùng) * (cuối cùng-1)) / 2 để đếm cho tất cả các cặp đảo ngữ
Cuối cùng, chúng tôi sẽ có một số lượng tất cả các từ đảo ngữ.
Kết quả là số lượt trả lại.

Ví dụ

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

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of total anagram substrings are: 3