สตริงเกือบซ้ำซ้ำ

o62_may15_repeats

ให้ S[i..j]S[i..j] แทน substring ของ SS ตั้งแต่ตำแหน่งที่ ii ถึง jj

หากเรากำลังพิจารณา substring S[i+1,i+L]S[i+1, i+L] โดยที่ความยาว LL เป็นเลขคู่ การเปรียบเทียบเพื่อนับจำนวนความผิดพลาด จะมีดังนี้

  • Si+1S_{i+1} และ Si+L/2+1S_{i+L/2+1}
  • Si+2S_{i+2} และ Si+L/2+2S_{i+L/2+2}
  • Si+3S_{i+3} และ Si+L/2+3S_{i+L/2+3}
  • …\dots
  • Si+L/2S_{i+L/2} และ Si+LS_{i+L}

แต่ถ้าเราพิจารณา substring S[i+2,i+L+1]S[i+2, i+L+1] ที่ความยาว LL เช่นกัน การเปรียบเทียบจะที่ต้องดูจะเป็น

  • Si+2S_{i+2} และ Si+L/2+2S_{i+L/2+2}
  • Si+3S_{i+3} และ Si+L/2+3S_{i+L/2+3}
  • Si+4S_{i+4} และ Si+L/2+4S_{i+L/2+4}
  • …\dots
  • Si+L/2+1S_{i+L/2+1} และ Si+L+1S_{i+L+1}

สังเกตว่าคู่ที่ต้องเปรียบเทียบนั้นเหมือนกันทุกคู่ยกเว้นคู่แรกและคู่สุดท้าย ดังนั้นเราสามารถใช้เทคนิค sliding window ในการคำนวณหาค่าความผิดพลาดของสตริงถัดไปได้ใน O(1)\mathcal{O}(1) และเราจะสามารถพิจารณาทุกสตริงที่มีความยาวค่า ๆ หนึ่งได้ใน O(n)\mathcal{O}(n)

เราจะทำเช่นนี้สำหรับทุก ๆ ความยาวที่เป็นไปได้ ทำให้เราได้อัลกอริธึมที่สามารถแก้ปัญหานี้ได้ในเวลา O(n2)\mathcal{O}(n^2)