Năm 2011, Tí bắt đầu tìm hiểu về thuật toán và mua rất nhiều sách để đọc. Hiện tại, Tí đang tìm hiểu về một thuật toán và muốn tìm các chương nói về thuật toán đó trong sách. Để làm việc này, Tí chỉ cần tìm các lần xuất hiện của tên thuật toán trong sách (tất nhiên, Tí hoàn toàn có thể viết một chương trình tự động). Tuy nhiên, một vấn đề nảy sinh là Tí có thể nhớ không chính xác tên của thuật toán mà bị nhầm một ký tự. Ví dụ, Tí có thể nhớ thuật toán tìm đường đi ngắn nhất là Diikstra thay vì Dijkstra.
Tiếc là Tí chưa đủ khả năng để viết một chương trình khắc phục vấn đề này, và Tí nhờ bạn: Hãy viết một chương trình tìm vị trí xuất hiện đầu tiên của một từ trong một văn bản, trong đó sai lệch ở một ký tự duy nhất có thể được bỏ qua. Do các cuốn sách của Tí đều sử dụng tiếng Việt có dấu, trong bài này chúng ta biểu diễn xâu bằng một dãy số, trong đó mỗi số thể hiện mã Unicode của một ký tự. (Mã Unicode gần giống như mã ASCII nhưng sử dụng 16 bit).
Input
- Dòng đầu ghi 2 số NP, NT thể hiện độ dài từ và văn bản. ( NP ~\leq 1000~, NT ~\leq 500000~)
- Dòng sau ghi ra NP số nguyên 16 bit thể hiện từ cần tìm.
- Dòng cuối ghi ra NT số nguyên 16 bit thể hiện văn bản.
Output
- Gồm một số duy nhất ghi ra vị trí xuất hiện đầu tiên của từ cần tìm. Nếu không tìm được in ra -1.
Giới hạn
- 50 % số test có NT ~\leq 5000~.
Sample Input
3 6
97 97 97
97 98 98 97 97 97
Sample Output
3
Note
- Giải thích: Từ phải tìm xuất hiện ở vị trí 3 và 4. Ta in ra vị trí đầu tiên
Comments