Hướng dẫn giải của Đếm tên
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho xâu S gồm tên các học sinh (cách nhau bởi khoảng trắng) và xâu T là một tên. Đếm số lần T xuất hiện trong S như một tên trọn vẹn.
Sub 1: Vét cạn, so khớp từng vị trí — ~O(|S| \cdot |T|)~
Thử mọi vị trí i trong S, cắt ra đoạn dài |T| bắt đầu tại i và so với T. Nếu bằng nhau, kiểm tra hai đầu đoạn đó có khoảng trắng (hoặc là đầu/cuối xâu) để chắc đó là một tên đầy đủ, không phải một phần của tên khác.
Kết quả chấm: 20/20 (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
getline(cin, s);
cin >> t;
// Vet can: voi moi vi tri i trong S, kiem tra xau con bang T co dung la mot ten (giua hai khoang trang hoac dau/cuoi xau)
int dem = 0;
int n = s.size(), m = t.size();
for (int i = 0; i + m <= n; i++) {
if (s.substr(i, m) != t) continue;
bool dauOK = (i == 0 || s[i - 1] == ' ');
bool cuoiOK = (i + m == n || s[i + m] == ' ');
if (dauOK && cuoiOK) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Tách từng tên bằng stringstream — ~O(|S|)~
Đọc S bằng stringstream, lần lượt lấy từng tên (ss >> ten) rồi so sánh với T. Cách này tự bỏ qua mọi khoảng trắng thừa nên không cần kiểm tra biên.
Bẫy: đọc S bằng getline vì S chứa khoảng trắng, còn T đọc bằng cin >> t. Nếu T không xuất hiện thì in 0.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
getline(cin, s);
cin >> t;
// Tach S thanh cac ten bang stringstream, so sanh tung ten voi T
stringstream ss(s);
string ten;
int dem = 0;
while (ss >> ten)
if (ten == t) dem++;
cout << dem << "\n";
return 0;
}
Bình luận