Trong bài toán này, chúng ta được cho một mảng các ký tự đều viết thường. Nhiệm vụ của chúng ta là Số lần xuất hiện tối đa của tiền tố trong mảng.
Ta cần đếm số lần xuất hiện của các tiền tố không rỗng có số lần xuất hiện tối đa.
Hãy xem ví dụ sau để hiểu bài toán:
Input : string = “xyyzkxyyzk” Output : 2
Phương pháp giải
Logic là hình dung rằng tiền tố của mảng phải luôn chứa ký tự đầu tiên của chuỗi và các lần xuất hiện lặp lại cũng vậy. Và ký tự đầu tiên của chuỗi rõ ràng là tiền tố với số ký tự ít nhất. Vì vậy tiền tố xuất hiện nhiều nhất chắc chắn là ký tự đầu tiên của chuỗi. Vì vậy công việc giờ giảm xuống tìm số lần xuất hiện của ký tự đầu tiên trong chuỗi.
Thuật toán
Đọc chuỗi chữ cái thường.
Tạo hàm trả về số lần xuất hiện tiền tố cần thiết.
Khởi tạo count=0.
Tìm tần suất ký tự đầu tiên của chuỗi.
In tần suất ký tự đầu tiên sẽ là số lần xuất hiện tối đa của tiền tố chuỗi.
Ví dụ
Chương trình minh họa cho giải pháp,
#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; }Kết quả
The maximum occurence of prefix in the array is 6