Đếm chuỗi BAB
Xem PDF
Điểm:
777
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho chuỗi \(s\) gồm \(n\) kí tự chữ cái in hoa. Nhiệm vụ của bạn là hãy đếm xem, xâu "BAB" xuất hiện bao nhiêu lần trong xâu \(s\). Biết rằng, các kí tự 'B,A,B' không nhất thiết liên tiếp nhau nhưng phải đảm bảo thứ tự.
Ví dụ 1: Cho xâu \(s='ABAGBA'\). Thì số lần xuất hiện của xâu "BAB" trong xâu \(s\) là: 1 lần.
Cụ thể đó là: 'ABAGBA'
Ví dụ 2: Cho xâu \(s='BACVBAB'\). Thì số lần xuất hiện của xâu "BAB" trong xâu \(s\) là: 4 lần.
Cụ thể đó là: 'BACVBAB' , 'BACVBAB', 'BACVBAB', 'BACVBAB'
Input
- Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
- \(t\) block tiếp theo, mỗi block có dạng như sau:
++ Dòng thứ nhất chứa số \(n(1\le n\le 100)\) - Thể hiện độ dài của xâu
++ Dòng thứ hai chứa xâu \(s\)
Output
- Ứng với testcase, hãy in kết quả ra màn hình.
Example
Test 1
Input
2
6
ABAGBA
7
BACVBABOutput
1
4
Bình luận
include <bits/stdc++.h>
using namespace std;
int dem_BAB(const string& s) {
int dem = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
if (s[i] == 'B') {
for (int j = i + 1; j < n; j++) {
if (s[j] == 'A') {
for (int k = j + 1; k < n; k++) {
if (s[k] == 'B') {
dem++;
}
}
}
}
}
}
return dem;
}
int main() {
int t,n;
string s;
cin >> t;
while (t--) {
cin>>n;
cin >> s;
cout << dem_BAB(s) << endl;
}
return 0;
}