418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 2

อัลกอริทึม

ให้สตริงใน $S'\,$ จับคู่กับสตริงใน $S\,$ ตัวแรกสุดที่เหมือนกัน ถ้าสตริงทุกตัวใน $S'\,$ ถูกจับคู่ได้หมดให้ตอบ "ใช่" ไม่เช่นั้นให้ตอบ "ไม่ใช่"

ให้ $i\,$ เป็นตัวแปรที่ชี้ไปยังสตริงที่กำลังพิจารณาในสตริง $S\,$

ให้ $j\,$ เป็นตัวแปรที่ชี้ไปยังสตริงที่กำลังพิจารณาในสตริง $S'\,$

<geshi lang="c"> FindSubString(S,m,S',n)

   {
    j = 1
    for i = 1 to m do
    {
     if S[i] = S'[j] then
         j = j + 1
    }
    if j > n then
         return 1
    else
         return 0
   }

</geshi>

การพิสูจน์ความถูกต้องของอัลกอริทึม

จะทำการพิสูจน์โดยใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ $Y_{i}\,$ คือตำแหน่งของสตริงใน $S\,$ ที่ถูกจับคู่กับสตริงตัวที่ $i\,$ ของ $S'\,$ ให้ $Y_{i}^{G}\,$ คือ ตำแหน่งของสตริงใน $S\,$ ที่ถูกจับคู่กับสตริงตัวที่ $i\,$ ของ $S'\,$ ที่ถูกจับคู่ตาม greedy algorithm ข้างต้น ส่วน $Y_{i}^{A}\,$ คือ ตำแหน่งของสตริงใน $S\,$ ที่ถูกจับคู่กับสตริงตัวที่ $i\,$ ของ $S'\,$ ที่ถูกจับคู่ตาม algorithm อื่น ๆ จะพิสูจน์ว่า $Y_{i}^{G}\leq Y_{i}^{A}\,$ เสมอ นั่นคือถ้ามีสตริงใน $S\,$ ที่เหมือนกับสตริงใน $S'\,$ ตำแหน่งที่เรากำลังพิจารณาแล้ว greedy algorithm จะสามารถจับคู่ได้เสมอ จะพิสูจน์โดยใช้ strong induction กรณี base case ให้ $i=1\,$ เนื่องจาก greedy algorithm จะจับคู่สตริงใน $S\,$ ตัวแรกสุดที่เหมือนกัน ดังนั้นถ้ามีสตริงใน $S\,$ ที่เหมือนกับสตริงตัวแรกใน $S'\,$ แล้ว $Y_{1}^{G}\leq Y_{1}^{A}\,$ เสมอ กรณี indutive step สมมติให้ $Y_{i}^{G}\leq Y_{i}^{A}\,$ สำหรับ $1\leq i<n\,$ พิจารณากรณีที่กำลังจับคู่ให้กับสตริงตัวที่ $n\,$ ใน $S'\,$ ถ้ามีสตริงใน $S\,$ ที่เหมือนกับสตริงใน $S'\,$ ตำแหน่งที่ $n\,$ แล้ว เนื่องจาก greedy algorithm จะจับตัวแรกที่เหมือนกัน ซึ่ง ถ้ามีแค่ตัวเดียวจะได้ว่า $Y_{n}^{G}=Y_{n}^{A}\,$ แต่ถ้ามีตัวที่เหมือนกันมากกว่าหนึ่งตัวแล้ว $Y_{n}^{G}<Y_{n}^{A}\,$ เนื่องจาก $Y_{i}^{G}\leq Y_{i}^{A}\,$ สำหรับ $1\leq i<n\,$ และ $Y_{n}^{G}\leq Y_{n}^{A}\,$ ดังนั้น $Y_{i}^{G}\leq Y_{i}^{A}\,$ สำหรับ $1\leq i\leq n\,$ จะได้ว่าสำหรับสตริง $n\,$ ตัวใน $S\,$ ถ้ามีสตริงที่เหมือนกันในสตริง $S\,$ แล้ว greedy algorithm จะตอบ "ใช่" เสมอ