Bản đồ gene
Các nhà khoa học vừa phát hiện ra bản đồ gene của một loài sinh vật trên Trái Đất có nguồn gốc từ rất lâu về trước (niên đại được xác định dựa trên các dấu vết khảo cổ học). Chuỗi gene di truyền của nó được biểu diễn bởi xâu kí tự S (chỉ gồm các kí tự A..Z). Nhằm đánh giá, nghiên cứu nó, họ muốn xem thử nó có đặc tính T hay không. T cũng được biểu diễn dưới dạng một xâu kí tự (với các kí tự A..Z), tương ứng với một đoạn gene. Người ta cho rằng, loại sinh vật này có tính chất T nói trên nếu chuỗi biểu diễn của T là một chuỗi con của S. Tức là, nếu ta lấy ra các kí tự liên tiếp của S tại vị trí nào đó thì có được T. Em hãy lập trình giải quyết bài toán trên. Dữ liệu: Nhập từ thiết bị vào chuẩn:
• 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.
Bản đồ gene
Các nhà khoa học vừa phát hiện ra bản đồ gene của một loài sinh vật trên Trái Đất có nguồn gốc từ rất lâu về trước (niên đại được xác định dựa trên các dấu vết khảo cổ học). Chuỗi gene di truyền của nó được biểu diễn bởi xâu kí tự S (chỉ gồm các kí tự A..Z). Nhằm đánh giá, nghiên cứu nó, họ muốn xem thử nó có đặc tính T hay không. T cũng được biểu diễn dưới dạng một xâu kí tự (với các kí tự A..Z), tương ứng với một đoạn gene. Người ta cho rằng, loại sinh vật này có tính chất T nói trên nếu chuỗi biểu diễn của T là một chuỗi con của S. Tức là, nếu ta lấy ra các kí tự liên tiếp của S tại vị trí nào đó thì có được T. Em hãy lập trình giải quyết bài toán trên. Dữ liệu: Nhập từ thiết bị vào chuẩn:
• 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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Á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.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Dành cho bạn Hot
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Với một dãy chưa được sắp xếp theo thứ tự, ta không có đủ cơ sở để loại bỏ một nửa dãy số ra khỏi phạm vi tìm kiếm sau khi so sánh phần tử giữa với giá trị x cần tìm.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Với mỗi chỉ số j, tồn tại tối đa một chỉ số i để h[j] – h[i] = d. Điều kiện h[j] - h[i] = d tương đương với h[i] = h[j] – d. Đặt h[j] – d = x, em có thê quy về bài toán tìm kiếm giá trị x trên dãy h. Sử dụng một biến kiểu boolean để ghi nhận kết quả tìm kiếm cho mỗi chỉ số j, em có thể tính tổng số lượng chỉ số j mà tồn tại i thoả mãn h[j] – h[i] = d, cũng chính là số cặp cần tìm.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập