Nội dung Bài tập
- Mã:
- KMP00
- Tên:
- KMP siêu cơ bản
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4801103089
Thuật toán KMP (Knuth–Morris–Pratt) là một thuật toán tìm kiếm chuỗi con (pattern) trong một chuỗi lớn (text) một cách hiệu quả, trong thời gian O(n) thay vì O(n*m) như cách duyệt truyền thống. Độ phức tạp thời gian: tính mảng LPS: O(m); tìm kiếm pattern trong trong text O(n) => Tổng O(m+n).
Quảng cáo
Cài đặt thuật toán KMP để tìm vị trí chuỗi con xuất hiện đầu tiên trong chuỗi lớn.
Input:
Dòng 1: Chuỗi lớn (viết thường, không dấu, không khoảng cách, không kí tự đặt biệt).
Dòng 2: Chuỗi cần tìm (viết thường, không dấu, không khoảng cách, không kí tự đặt biệt).
Output:
Nếu có in ra vị trí đầu tiên xuất hiện.
Nếu không có in ra -1.
Ví dụ:
Input
Output
abababcababc
ababc
2
Ví dụ:
Input
Output
abababcababc
ababb
-1
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
LTNC_Thứ 3