Hướng dẫn giải của STR08: Đế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
Đếm số lần xuất hiện của xâu T trong xâu S (S dài tối đa 1500 ký tự). Mỗi lần xuất hiện được tính tại mọi vị trí bắt đầu, kể cả khi các lần chồng lên nhau.
Sub 1: So sánh từng ký tự — ~O(|S| · |T|)~
Với mỗi vị trí bắt đầu i, so sánh lần lượt từng ký tự của T với S. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
getline(cin, s);
getline(cin, t);
if (!s.empty() && s.back() == '\r') s.pop_back();
if (!t.empty() && t.back() == '\r') t.pop_back();
// Vét cạn: thử mọi vị trí i, so sánh từng ký tự của T với S
int cnt = 0;
int n = s.size(), m = t.size();
for (int i = 0; i + m <= n; i++) {
bool ok = true;
for (int j = 0; j < m && ok; j++)
if (s[i + j] != t[j]) ok = false;
if (ok) cnt++;
}
cout << cnt << "\n";
return 0;
}
Sub 2: Dùng find — ~O(|S| · |T|)~
Dùng std::string::find để tìm lần xuất hiện tiếp theo. Sau mỗi lần tìm được tại vị trí pos, tiếp tục tìm từ pos + 1 để không bỏ sót lần xuất hiện chồng nhau. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
getline(cin, s);
getline(cin, t);
if (!s.empty() && s.back() == '\r') s.pop_back();
if (!t.empty() && t.back() == '\r') t.pop_back();
// Dùng find để tìm lần xuất hiện tiếp theo, bắt đầu tìm từ vị trí ngay sau lần vừa thấy
int cnt = 0;
size_t pos = s.find(t);
while (pos != string::npos) {
cnt++;
pos = s.find(t, pos + 1);
}
cout << cnt << "\n";
return 0;
}
Bình luận