ขั้นตอนวิธีการค้นหาคำแบบซี

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีนี้ คือ ขั้นตอนวิธีที่เอาไว้ใช้ในการหารูปแบบคำ(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
ตัวอย่าง
=== 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
Z(1) = 0 , lt =0, rt = 0
2. ต่อไปขยับอินเด็กซ์ k เป็น k= 2
ที่ k=2 S(2) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
Z(2) = 0 , lt =0, rt = 0
3. ต่อไปขยับอินเด็กซ์ k เป็น k= 3
ที่ k=3 S(3) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 0
Z(3) = 0 , lt =0, rt = 0
4. ต่อไปขยับอินเด็กซ์ k เป็น k= 4
ที่ k=4 S(4) ไม่เหมือนกับ S(0) ดังนั้นจึงไม่เกิด Z-box ขึ้น ค่าของอินเด็กซ์ lt และ rt ก็ยังคงเป็น 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
Z(5) = 3, lt =5, rt = 7
6. ต่อไปขยับอินเด็กซ์ k เป็น k= 6
ที่  k = 6 อยู่ใน substring ก่อนหน้า ซึ่ง(rt = 7) และ substring ย่อยก่อนหน้านี้เริ่มต้นที่ k-lt (6-5) โดย Z(1) = 0  ซึ่ง 
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 0:
lt = k
rt = k+n-1
else:
p = k-lt
right_part_len = rt-k+1
if Z[p]
== อ้างอิง ==
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/
ขั้นตอนวิธี