Hướng dẫn giải của Từ dài nhất (Đề HSG Quảng Bình 2021)
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
Xâu S (tối đa 255 ký tự) gồm các ký tự chữ, số, * và dấu cách. Từ là dãy ký tự liên tiếp không chứa dấu cách, nên cần tìm độ dài lớn nhất của một đoạn liên tiếp không có dấu cách.
Sub 1: Vét cạn — ~O(n^3)~
Thử mọi đoạn con s[i..j], với mỗi đoạn kiểm tra xem có dấu cách hay không. Nếu không có thì đoạn đó là một từ và ta cập nhật độ dài lớn nhất. Đúng với mọi test nhưng phải kiểm tra từng đoạn.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LWORD.INP", "r")) { freopen("LWORD.INP", "r", stdin); freopen("LWORD.OUT", "w", stdout); }
string s;
getline(cin, s);
int n = s.size();
int best = 0;
// Vet can: thu moi doan con s[i..j], neu doan do khong chua dau cach thi la mot tu
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool ok = true;
for (int k = i; k <= j; k++)
if (s[k] == ' ' || s[k] == '\r') { ok = false; break; }
if (ok) best = max(best, j - i + 1);
}
}
cout << best << "\n";
return 0;
}
Sub 2: Đếm liên tiếp một lần duyệt — ~O(n)~
Duyệt xâu một lần, biến cur đếm độ dài từ đang xét. Gặp ký tự khác dấu cách thì cur tăng và cập nhật best; gặp dấu cách thì đặt cur = 0 vì từ vừa kết thúc. Lưu ý xử lý ký tự \r (nếu có) như dấu ngăn cách.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LWORD.INP", "r")) { freopen("LWORD.INP", "r", stdin); freopen("LWORD.OUT", "w", stdout); }
string s;
getline(cin, s);
int best = 0, cur = 0;
// Duyet mot lan: cur la do dai tu dang xet, gap dau cach thi reset ve 0
for (char c : s) {
if (c == ' ' || c == '\r') cur = 0;
else {
cur++;
best = max(best, cur);
}
}
cout << best << "\n";
return 0;
}
Bình luận