Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

V11STR - Tìm xâu

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 <= 1000, NT <= 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 <= 5000.

Example

Input:
3 6
97 97 97
97 98 98 97 97 97

Output: 3
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.

Được gửi lên bởi:VOJ Team
Ngày:2011-01-03
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 2011
Tác giả: Khúc Anh Tuấn

hide comments
2018-10-30 07:10:17
1 Hit AC =w=
Chưa nghĩ được O(N) :p
frostpixel aka.How 2 AC
2018-08-03 04:36:08
nhật hào sạch tới rồi à


Last edit: 2018-08-03 04:36:39
2018-08-03 04:21:57
nhật hào sạch đã đánh dấu <3
2014-12-08 09:03:40 NTT
PS cho hỏi mình làm O(N) sao chỉ được có 60 nhỉ???
2012-05-28 15:19:08 123
so nguyen 16 bit max la bn the?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.