Trong bài toán này, chúng ta được cung cấp một mảng các ký tự đều là chữ thường. Nhiệm vụ của chúng tôi là Số tiền tố xuất hiện tối đa trong Mảng .
Chúng tôi cần đếm số lần xuất hiện của các tiền tố không trống có số lần xuất hiện là tối đa.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : string = “xyyzkxyyzk” Output : 2
Phương pháp tiếp cận giải pháp
Logic là hình dung rằng tiền tố của một mảng phải luôn, rõ ràng, chứa ký tự đầu tiên của chuỗi và do đó, các lần xuất hiện lặp lại của nó cũng vậy. Và ký tự đầu tiên của một chuỗi rõ ràng là một tiền tố có số ký tự ít nhất. Vì vậy, tiền tố xuất hiện tối đa chắc chắn sẽ là ký tự đầu tiên của chuỗi. Vì vậy, công việc bây giờ đã được giảm bớt để tìm số ký tự đầu tiên trong chuỗi.
Thuật toán
-
Đọc một chuỗi các bảng chữ cái viết thường.
-
Tạo một hàm để trả về số lượng tiền tố bắt buộc.
-
Số lần khởi tạo =0.
-
Tìm tần suất của ký tự đầu tiên của chuỗi.
-
In tần suất của ký tự đầu tiên của chuỗi mà cuối cùng sẽ là tần suất xuất hiện tối đa của một tiền tố của chuỗi.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int findPrefixOccurence(string str){
char chars = str[0];
int countOccrence = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == chars)
countOccrence++;
}
return countOccrence;
}
int main(){
string str = "xyyzxxyyzxyxx";
cout<<"The maximum occurence of prefix in the array is "<<findPrefixOccurence(str);
return 0;
} Đầu ra
The maximum occurence of prefix in the array is 6