Tìm số vị trí cân bằng trong chuỗi trong C ++

Giả sử chúng ta có một chuỗi. Chúng ta phải tìm số vị trí cân bằng trong chuỗi đó từ phần bên trái và bên phải của chuỗi chứa các ký tự giống nhau. Tần số của các ký tự không quan trọng. Vậy nếu chuỗi là “ABAABA” thì số vị trí cân bằng là 3. Các vị trí này là AB | AABA, ABA | ABA, ABAA | BA.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo một số cách tiếp cận hiệu quả. Sau khi duyệt qua chuỗi, chúng tôi đầu tiên cảm thấy đúng [] với số lượng tất cả các ký tự. Sau đó lướt qua chuỗi từ trái sang phải. Đối với mỗi ký tự, chúng tôi tăng số lượng của nó ở bên trái [] và giảm số lượng ở bên phải. Đối với bất kỳ điểm nào đang được duyệt qua, nếu tất cả các ký tự có giá trị khác 0 ở bên trái cũng có giá trị khác 0 ở bên phải và ngược lại cũng đúng. Sau đó, tăng kết quả.

Ví dụ

#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;
int countBalancePoints(string str) {
   int left[MAX_CHAR] = {0};
   int right[MAX_CHAR] = {0};
   for (int i=0; i<str.length(); i++)
   right[str[i]]++;
   int count = 0;
   for (int i=0; i < str.length() ; i++) {
      left[str[i]]++;
      right[str[i]]--;
      int j;
      for (j=0; j<MAX_CHAR; j++) {
         if ( (left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
         break;
      }
      if (j == MAX_CHAR)
         count++;
   }
   return count;
}
int main() {
   char str[] = "ABAABA";
   cout << "Number of balance points: " << countBalancePoints(str);
}

Đầu ra

Number of balance points: 3