ขั้นตอนวิธีการค้นหาคำแบบซี
หลักการ > Z-value คืออะไร > ตัวอย่างการสร้าง Z-value

1. Z algorithm จะเริ่มที่ k = 1, lt = 0, rt = 0  ให้ Z(0) คือความยาวของ Z-array = 15 ที่ k=1 S(1) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |  |
Z(1) = 0 , lt =0, rt = 0
2. ต่อไปขยับอินเด็กซ์ k เป็น k= 2
ที่ k=2 S(2) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 |  |  |  |  |  |  |  |  |  |  |  |  |
Z(2) = 0 , lt =0, rt = 0
3. ต่อไปขยับอินเด็กซ์ k เป็น k= 3
ที่ k=3 S(3) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 |  |  |  |  |  |  |  |  |  |  |  |
Z(3) = 0 , lt =0, rt = 0
4. ต่อไปขยับอินเด็กซ์ k เป็น k= 4
ที่ k=4 S(4) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 |  |  |  |  |  |  |  |  |  |  |
Z(4) = 0 , lt =0, rt = 0
5. ต่อไปขยับอินเด็กซ์ k เป็น k= 5
ที่ k=5 S(5) เหมือน S(0), S(6) เหมือน S(1) และ S(7) เหมือน S(2) ดังนั้น Z(5) = 3 และเกิด Z-box ทำให้ lt = 5 และ rt = 7
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 |  |  |  |  |  |  |  |  |  |
Z(5) = 3, lt =5, rt = 7
6. ต่อไปขยับอินเด็กซ์ k เป็น k= 6
ที่  k = 6 อยู่ใน substring ก่อนหน้า ซึ่ง(rt = 7) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (6-5) โดย Z(1) = 0  ซึ่ง < substring ที่เหลือ S[6…7] ดังนั้น Z(6) = Z(1) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 |  |  |  |  |  |  |  |  |
Z(6) = 0, lt = 5, rt = 7
7. ต่อไปขยับอินเด็กซ์ k เป็น k= 7
ที่  k = 7 อยู่ใน substring ก่อนหน้า ซึ่ง(rt = 7) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (7-5) โดย Z(2) = 0  ซึ่ง < substring ที่เหลือ S[7…7] ดังนั้น Z(7) = Z(2) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |  |  |  |  |  |  |  |
Z(7) = 0, lt = 5, rt = 7
8. ต่อไปขยับอินเด็กซ์ k เป็น k= 8
ที่ k=8 S(8) เหมือน S(0), S(9) เหมือน S(1) และ S(10) เหมือน S(2) ดังนั้น S(8) = 3 และเกิด Z-box ทำให้ lt = 8 และ rt = 10
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 |  |  |  |  |  |  |
Z(8) = 3, lt = 8, rt = 10
9. ต่อไปขยับอินเด็กซ์ k เป็น k= 9
ที่  k = 9 อยู่ใน substring ก่อนหน้า ซึ่ง (rt = 10) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (9-8) โดย Z(1) = 0  ซึ่ง < substring ที่เหลือ S[9…10] ดังนั้น Z(9) = Z(1) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 |  |  |  |  |  |
Z(9) = 0, lt = 8, rt = 10
10. ต่อไปขยับอินเด็กซ์ k เป็น k= 10
ที่  k = 10 อยู่ใน substring ก่อนหน้า ซึ่ง r = 10 และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (10-8) โดย Z(2) = 0  ซึ่ง < substring ที่เหลือ S[10…10] ดังนั้น Z(10) = Z(2) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 |  |  |  |  |
Z(10) = 0, lt = 8, rt = 10
11.  ต่อไปขยับอินเด็กซ์ k เป็น k= 11
ที่ k=11 S(11) เหมือน S(0), S(12) เหมือน S(1), S(13) เหมือน S(2) และ S(14) เหมือน S(3) ดังนั้น Z(11) = 4 และเกิด Z-box ทำให้ lt = 11 และ rt = 14
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 4 |  |  |  |
Z(11) = 4, lt = 11, rt = 14
12.  ต่อไปขยับอินเด็กซ์ k เป็น k= 12
ที่  k = 12 อยู่ใน substring ก่อนหน้า ซึ่ง (rt = 14) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (12-11) โดย Z(1) = 0  ซึ่ง < substring ที่เหลือ S[12…14] ดังนั้น Z(12) = Z(1) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 4 | 0 |  |  |
Z(12) = 0, lt = 11, rt = 14
13.  ต่อไปขยับอินเด็กซ์ k เป็น k= 13
ที่  k = 13 อยู่ใน substring ก่อนหน้า ซึ่ง (rt = 14) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (13-11) โดย Z(2) = 0  ซึ่ง < substring ที่เหลือ S[13…14] ดังนั้น Z(13) = Z(2) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 4 | 0 | 0 |  |
Z(13) = 0, lt = 11, rt = 14
14.  ต่อไปขยับอินเด็กซ์ k เป็น k= 14
ที่  k = 14 อยู่ใน substring ก่อนหน้า ซึ่ง (rt = 14) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (14-11) โดย Z(3) = 0  ซึ่ง < substring ที่เหลือ S[14…14] ดังนั้น Z(14) = Z(3) = 0 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 4 | 0 | 0 | 0 |
Z(14) = 0, lt = 11, rt = 14
15.   Z-array ที่สมบูรณ์ จะเป็นดังนี้
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New  string S | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
| Z-value | 15 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0 | 0 | 4 | 0 | 0 | 0 |