Ipsc2012

หน้านี้รวมคำแปลโจทย์จากการแข่งขัน Internet Problem Solving Contest ปี 2012

Problem E – Evil matching

ให้ลำดับของจำนวนเต็มบวก T = t₁,t₂,…,t_n (text) และ P = p₁,p₂,…,p_m (pattern). นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p₁ = t_k, p₂ = t_k+1, …, และ p_m = t_k+m−1. เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm.

เพื่อลดความน่าเบื่อจากอะไรง่าย ๆ เราจะนิยามอะไรให้ยากขึ้นสักหน่อย เราจะกล่าวว่า P evil-match กับ T ที่ตำแหน่ง k ถ้ามีลำดับของดัชนี k = a₀ < a₁ < ⋯ < a_m ที่

• t_a0 + t_a0+1 + ⋯ + t_a1−1 = p₁
• t_a1 + t_a1+1 + ⋯ + t_a2−1 = p₂
• ...
• t_am−1 + t_am−1+1 + ⋯ + t_am−1 = p_m

นั่นคือ เราสามารถที่จะรวมข้อมูลใน text เป็นกลุ่ม ๆ เข้าด้วยกันก่อนที่จะไปจับคู่กับ pattern ยกตัวอย่างเช่น ถ้าเรามี T = 1,2,1,1,3,2 และ P = 3,2, เราจะมีสอง evil-matches: อันแรกที่ตำแหน่ง k = 1 (with a1 = 3,a2 = 5), อันที่สองที่ k = 5 (with a1 = 6,a2 = 7).