Hướng dẫn giải của STR09: Tì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
Tìm vị trí xuất hiện đầu tiên của xâu T trong xâu S, đánh số vị trí từ 1. Nếu không có thì in 0.
Sub 1: So sánh từng ký tự — ~O(|S| · |T|)~
Thử từng vị trí bắt đầu i, so sánh từng ký tự. Gặp lần đầu tiên thì in i + 1 rồi dừng. Đạ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ử từng vị trí bắt đầu, so sánh từng ký tự
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) { cout << i + 1 << "\n"; return 0; } // vị trí đánh số từ 1
}
cout << 0 << "\n";
return 0;
}
Sub 2: Dùng find — ~O(|S| · |T|)~
std::string::find trả về vị trí đánh số từ 0 hoặc npos khi không thấy, nên đổi sang số từ 1 bằng cách cộng 1; npos thì in 0. Đạ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();
// find trả về vị trí từ 0, đổi sang từ 1; không thấy thì trả về npos
size_t pos = s.find(t);
if (pos == string::npos) cout << 0 << "\n";
else cout << pos + 1 << "\n";
return 0;
}
Bình luận