Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีนี้ คือ ขั้นตอนวิธีที่เอาไว้ใช้ในการหารูปแบบคำ(pattern)ในคำ(text) โดยเราให้ความยาวของคำ(text) เป็น n และคำเป็น m แล้วผลรวมของเวลาที่ใช้ในการประมวลผล คือ O(n+m) ซึ่งจะเหมือนกับขั้นตอนวิธีของคนูธ-มอร์ริส-แพรตต์
ขั้นตอนวิธี-ซี เป็นขั้นตอนวิธีแบบตรงไปตรงมา (Brute-Force algorithm) ซึ่งเกิดจากการทำงานวนลูปรูปแบบคำ(pattern) n ครั้ง และวนรูปคำ(text) อีก m ครั้ง ทำให้ประสิทธิภาพของเวลาการทำงานของโปรแกรมเป็น O(n+m)
หลักการ
หลักการของขั้นตอนวิธีแบบซีนั้น แบ่งขั้นตอนการทำงานออกเป็น 3 หลัก
1. สร้างสตริงขึ้นมาใหม่ ซึ่งเกิดจากนำเอา Pattern + $ + Text โดยเครื่องหมาย $ เป็นเครื่องหมายที่เราสมมติขึ้นมาเพื่อขั้นระหว่าง Pattern และ Text เพื่อให้ง่ายต่อการตรวจสอบ
ตัวอย่าง
Text = “ABCABCABCD” และ Pattern = “ABCD”
New string S = “ABCD$ABCABCABCD”
2. สร้างอาเรย์ขึ้นมา 1 อาเรย์ เรียกว่า Z-array ซึ่งภายในจะประกอบไปด้วย Z-Value และ Z-value จะทำให้เกิด Z-box ขึ้น
3. เมื่อมีคำที่เหมือนกับ Pattern เกิดขึ้น เราสามารถสังเกตได้จาก Z-value ที่มีความยาวเท่ากับ ความยาวของ Pattren
Z-array คืออะไร
Z-array คืออาเรย์ใหม่ ที่เกิดจากการต่อกันระหว่าง Pattern กับ Text ซึ่งจะมีผลในการหาค่าของ Z-value และยังเป็นขั้นตอนที่สำคัญมากใน string matching ด้วยวิธี Z-algorithm
ตัวอย่าง
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| New string | A | B | C | D | $ | A | B | C | A | B | C | A | B | C | D |
Z-value คืออะไร
Z-value คือค่าตัวเลขที่ได้จากการทำงานวนลูปซ้อนกัน โดยลูปนอกเป็นอินเด็กซ์ที่ทุกตัวอักษร (สมมติเป็น index k) และลูปในคืออินเด็กซ์ที่ Patter ใน New String S
หลักการสร้าง Z-value
เราต้องสมมติ Z-box ขึ้นมา ซึ่ง Z-box นี้ คือ กล่องสตริงย่อยที่ตรงกับ Pattern ที่อยู่ด้านหน้า โดยเราจะให้ lt คือ ตัวอักษรด้านซ้ายสุดของกล่อง และ rt คือ ตัวอักษรด้านขวามือของกล่อง
ตัวอย่างการสร้าง 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
| 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
| 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
| 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
| 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
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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 โดยไม่ต้องมีการคำนวณเพิ่มเติม
| 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 ที่สมบูรณ์ จะเป็นดังนี้
| 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 |
มี Pattern อยู่ใน Text กี่ตำแหน่ง
เราจะทราบได้อย่างไรว่ามี Pattern อยู่ใน Text หรือไม่??? Pattern = “ABCD” ซึ่งมีความยาวเป็น 4 และ เราจะพบ Z-value ที่มีค่าเท่ากับ 4 ที่ตำแหน่งที่ 11 ของ Z-array ซึ่ง ถ้าเอา Z(11) - |Pattern+1| = 11-5 = 6 ซึ่ง ตรงกับ Text ในตำแหน่งที่ 6 พอดี
| 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 |
ประสิทธิภาพการทำงาน
เนื่องจากการทำงานวนลูปรูปแบบคำ(pattern) n ครั้ง และวนรูปคำ(text) อีก m ครั้ง ทำให้ประสิทธิภาพของเวลาการทำงานของโปรแกรมเป็น O(n+m)
โค้ดตัวอย่าง
def search_without_sentinel(text,pattern): s = pattern + text Z = [0] * len(s) Z[0] = len(s) rt = 0 lt = 0 occurrence = [] for k in range(1,len(s)): if k > rt: n=0 while n+k < len(s) and s[n] == s[n+k]: n+= 1 Z[k] = n if n>0: lt = k rt = k+n-1 else: p = k-lt right_part_len = rt-k+1 if Z[p]< right_part_len: Z[k] = Z[p] else: i = rt+1 while i<len(s) and s[i] == s[i-k]: i+=1 Z[k] = i-k lt = k rt = i -1 Z[k] = min(len(pattern),Z[k]) if Z[k] == len(pattern): occurrence.append(k-len(pattern)) return occurrence อ้างอิง
Ivan Yurchenko. (October 15, 2013), "Z algorithm" , Yet another programming blog, 25 เมษายน 2561, https://ivanyu.me/blog/2013/10/15/z-algorithm/
Utkarsh Trivedi, "Z algorithm (Linear time pattern searching Algorithm)" , GeeksforGeeks, 25 เมษายน 2561, https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
inwithyakarkhxmphiwetxr khntxnwithini khux khntxnwithithiexaiwichinkarharupaebbkha pattern inkha text odyeraihkhwamyawkhxngkha text epn n aelakhaepn m aelwphlrwmkhxngewlathiichinkarpramwlphl khux O n m sungcaehmuxnkbkhntxnwithikhxngkhnuth mxrris aephrtt khntxnwithi si epnkhntxnwithiaebbtrngiptrngma Brute Force algorithm sungekidcakkarthanganwnluprupaebbkha pattern n khrng aelawnrupkha text xik m khrng thaihprasiththiphaphkhxngewlakarthangankhxngopraekrmepn O n m hlkkar hlkkarkhxngkhntxnwithiaebbsinn aebngkhntxnkarthanganxxkepn 3 hlk 1 srangstringkhunmaihm sungekidcaknaexa Pattern Text odyekhruxnghmay epnekhruxnghmaythierasmmtikhunmaephuxkhnrahwang Pattern aela Text ephuxihngaytxkartrwcsxb twxyang Text ABCABCABCD aela Pattern ABCD New string S ABCD ABCABCABCD 2 srangxaerykhunma 1 xaery eriykwa Z array sungphayincaprakxbipdwy Z Value aela Z value cathaihekid Z box khun 3 emuxmikhathiehmuxnkb Pattern ekidkhun erasamarthsngektidcak Z value thimikhwamyawethakb khwamyawkhxng Pattren Z array khuxxair Z array khuxxaeryihm thiekidcakkartxknrahwang Pattern kb Text sungcamiphlinkarhakhakhxng Z value aelayngepnkhntxnthisakhymakin string matching dwywithi Z algorithm twxyang position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string A B C D A B C A B C A B C DZ value khuxxair Z value khuxkhatwelkhthiidcakkarthanganwnlupsxnkn odylupnxkepnxinedksthithuktwxksr smmtiepn index k aelalupinkhuxxinedksthi Patter in New String S hlkkarsrang Z value eratxngsmmti Z box khunma sung Z box ni khux klxngstringyxythitrngkb Pattern thixyudanhna odyeracaih lt khux twxksrdansaysudkhxngklxng aela rt khux twxksrdankhwamuxkhxngklxng twxyangkarsrang Z value 1 Z algorithm caerimthi k 1 lt 0 rt 0 ih Z 0 khuxkhwamyawkhxng Z array 15 thi k 1 S 1 imehmuxnkb S 0 dngnncungimekid Z box khun khakhxngxinedks lt aela rt kyngkhngepn 0 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 Z 1 0 lt 0 rt 0 2 txipkhybxinedks k epn k 2 thi k 2 S 2 imehmuxnkb S 0 dngnncungimekid Z box khun khakhxngxinedks lt aela rt kyngkhngepn 0 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 Z 2 0 lt 0 rt 0 3 txipkhybxinedks k epn k 3 thi k 3 S 3 imehmuxnkb S 0 dngnncungimekid Z box khun khakhxngxinedks lt aela rt kyngkhngepn 0 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 Z 3 0 lt 0 rt 0 4 txipkhybxinedks k epn k 4 thi k 4 S 4 imehmuxnkb S 0 dngnncungimekid Z box khun khakhxngxinedks lt aela rt kyngkhngepn 0 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 Z 4 0 lt 0 rt 0 5 txipkhybxinedks k epn k 5 thi k 5 S 5 ehmuxn S 0 S 6 ehmuxn S 1 aela S 7 ehmuxn S 2 dngnn Z 5 3 aelaekid Z box thaih lt 5 aela rt 7 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 Z 5 3 lt 5 rt 7 6 txipkhybxinedks k epn k 6 thi k 6 xyuin substring kxnhna sung rt 7 aela substring yxykxnhnanierimtnthi k lt 6 5 ody Z 1 0 sung lt substring thiehlux S 6 7 dngnn Z 6 Z 1 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 Z 6 0 lt 5 rt 7 7 txipkhybxinedks k epn k 7 thi k 7 xyuin substring kxnhna sung rt 7 aela substring yxykxnhnanierimtnthi k lt 7 5 ody Z 2 0 sung lt substring thiehlux S 7 7 dngnn Z 7 Z 2 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 Z 7 0 lt 5 rt 7 8 txipkhybxinedks k epn k 8 thi k 8 S 8 ehmuxn S 0 S 9 ehmuxn S 1 aela S 10 ehmuxn S 2 dngnn S 8 3 aelaekid Z box thaih lt 8 aela rt 10 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 Z 8 3 lt 8 rt 10 9 txipkhybxinedks k epn k 9 thi k 9 xyuin substring kxnhna sung rt 10 aela substring yxykxnhnanierimtnthi k lt 9 8 ody Z 1 0 sung lt substring thiehlux S 9 10 dngnn Z 9 Z 1 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 Z 9 0 lt 8 rt 10 10 txipkhybxinedks k epn k 10 thi k 10 xyuin substring kxnhna sung r 10 aela substring yxykxnhnanierimtnthi k lt 10 8 ody Z 2 0 sung lt substring thiehlux S 10 10 dngnn Z 10 Z 2 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 Z 10 0 lt 8 rt 10 11 txipkhybxinedks k epn k 11 thi k 11 S 11 ehmuxn S 0 S 12 ehmuxn S 1 S 13 ehmuxn S 2 aela S 14 ehmuxn S 3 dngnn Z 11 4 aelaekid Z box thaih lt 11 aela rt 14 position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 4 Z 11 4 lt 11 rt 14 12 txipkhybxinedks k epn k 12 thi k 12 xyuin substring kxnhna sung rt 14 aela substring yxykxnhnanierimtnthi k lt 12 11 ody Z 1 0 sung lt substring thiehlux S 12 14 dngnn Z 12 Z 1 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 4 0 Z 12 0 lt 11 rt 14 13 txipkhybxinedks k epn k 13 thi k 13 xyuin substring kxnhna sung rt 14 aela substring yxykxnhnanierimtnthi k lt 13 11 ody Z 2 0 sung lt substring thiehlux S 13 14 dngnn Z 13 Z 2 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 4 0 0 Z 13 0 lt 11 rt 14 14 txipkhybxinedks k epn k 14 thi k 14 xyuin substring kxnhna sung rt 14 aela substring yxykxnhnanierimtnthi k lt 14 11 ody Z 3 0 sung lt substring thiehlux S 14 14 dngnn Z 14 Z 3 0 odyimtxngmikarkhanwnephimetim position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DNew string S A B C D A B C A B C A B C DZ 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 thismburn caepndngni position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 4 0 0 0mi Pattern xyuin Text kitaaehnng eracathrabidxyangirwami Pattern xyuin Text hruxim Pattern ABCD sungmikhwamyawepn 4 aela eracaphb Z value thimikhaethakb 4 thitaaehnngthi 11 khxng Z array sung thaexa Z 11 Pattern 1 11 5 6 sung trngkb Text intaaehnngthi 6 phxdi position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14New string S A B C D A B C A B C A B C DZ value 15 0 0 0 0 3 0 0 3 0 0 4 0 0 0prasiththiphaphkarthanganenuxngcakkarthanganwnluprupaebbkha pattern n khrng aelawnrupkha text xik m khrng thaihprasiththiphaphkhxngewlakarthangankhxngopraekrmepn O n m okhdtwxyangdef search without sentinel text pattern s pattern text Z 0 len s Z 0 len s rt 0 lt 0 occurrence for k in range 1 len s if k gt rt n 0 while n k lt len s and s n s n k n 1 Z k n if n gt 0 lt k rt k n 1 else p k lt right part len rt k 1 if Z p lt right part len Z k Z p else i rt 1 while i lt len s and s i s i k i 1 Z k i k lt k rt i 1 Z k min len pattern Z k if Z k len pattern occurrence append k len pattern return occurrencexangxingIvan Yurchenko October 15 2013 Z algorithm Yet another programming blog 25 emsayn 2561 https ivanyu me blog 2013 10 15 z algorithm Utkarsh Trivedi Z algorithm Linear time pattern searching Algorithm GeeksforGeeks 25 emsayn 2561 https www geeksforgeeks org z algorithm linear time pattern searching algorithm