Với giải Câu Fcs30 trang 56 SBT Tin học 11 Cánh diều chi tiết trong Bài 7: Lập trình giải bài toán tìm kiếm giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập trong SBT Tin học 11. Mời các bạn đón xem:
Giải SBT Tin học 11 Bài 7: Lập trình giải bài toán tìm kiếm
Câu Fcs30 trang 56 SBT Tin học 11: Bản đồ gene
• Dòng đầu tiên chứa xâu S.
• Dòng thứ hai chứa xâu T.
Kết quả: Hiển thị ở thiết bị ra chuẩn các số nguyên là những vị trí mà ta tìm thấy được T ở trong S.
Lời giải:
Áp dụng lát cắt danh sách, việc cài đặt khá đơn giản.
S = input ()
T = input ()
for i in range (len (S) - len (T) + 1):
if T == S[i: i+len (T)]:
print (i+1, end = " ")
Mở rộng: Trong thực tế, thuật toán trên chưa đủ hiệu quả, vì việc so sánh hai xấu có độ phức tạp là len(T). Vậy độ phức tạp của thuật toán trên là len(S) x len(T) trong trường hợp xấu nhất. Áp dụng tư tưởng làm mịn dần thuật toán, người ta đã phát minh ra các thuật toán so khớp xâu:
– Hash (thường gặp trong mật mã học – cryptography).
– KMP (tận dụng những kí tự đã được so sánh trước đó để không phải so sánh lại từ đầu).
- Z function.
Em có thể tìm đọc để tăng thêm niềm đam mê với thuật toán.
Xem thêm lời giải Sách bài tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Câu Fcs30 trang 56 SBT Tin học 11: Bản đồ gene...
Xem thêm các bài giải SBT Tin học lớp 11 Cánh diều hay, chi tiết khác: