อัลกอริทึมการค้นหาข้อความเป็นวิธีการพื้นฐานในการประมวลผลข้อความและการดึงข้อมูล อัลกอริทึมนี้ช่วยให้เราสามารถค้นหาและระบุการเกิดขึ้นของสตริงย่อย(หรือรูปแบบ) ภายในข้อความขนาดใหญ่
มันทำงานอย่างไร
- เริ่มต้นด้วยข้อความ(หรือเอกสาร) ที่ใหญ่ขึ้นและสตริงย่อยเพื่อค้นหา
- วนซ้ำผ่านอักขระแต่ละตัวของข้อความตามลำดับ
- เปรียบเทียบสตริงย่อยกับส่วนของข้อความที่มีความยาวเท่ากันกับสตริงย่อย หากพบการแข่งขัน ให้บันทึกตำแหน่งปัจจุบัน
- ย้ายไปยังตำแหน่งถัดไปและทำการเปรียบเทียบต่อไป
ตัวอย่าง
พิจารณาข้อความ: "ลองค้นหาสตริงย่อยภายในข้อความนี้เพื่อดูว่าอัลกอริทึมทำงานอย่างไร"
และสตริงย่อยเพื่อค้นหา: "substring"
- เริ่มที่ตำแหน่ง 0 เปรียบเทียบ
Let'
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 1 เปรียบเทียบ
et's
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 2 เปรียบเทียบ
t's
" กับ "substring" ไม่ตรงกัน - ย้ายไปตำแหน่ง 3 เปรียบเทียบ
's s
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่งที่ 4 เปรียบเทียบ
se
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 5 เปรียบเทียบ
sea
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 6 เปรียบเทียบ
earc
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 7 เปรียบเทียบ
arch
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 8 เปรียบเทียบ
rch
" กับ "substring" ไม่ตรงกัน - เลื่อนไปที่ตำแหน่ง 9 เปรียบเทียบ
ch w
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 10 เปรียบเทียบ
h wi
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 11 เปรียบเทียบ "
wit
กับ "substring" ไม่ตรงกัน - ย้ายไปตำแหน่ง 12 เปรียบเทียบ
with
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 13 เปรียบเทียบ
ithi
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 14 เปรียบเทียบ
thin
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 15 เปรียบเทียบ
hinn
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 16 เปรียบเทียบ
in t
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 17 เปรียบเทียบ
n th
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 18 เปรียบเทียบ "
thi
กับ "substring" ไม่ตรงกัน - ย้ายไปตำแหน่ง 19 เปรียบเทียบ
this
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 20 เปรียบเทียบ
his
" กับ "substring" ไม่ตรงกัน - ย้ายไปที่ตำแหน่ง 21 เปรียบเทียบ
is t
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 22 เปรียบเทียบ
s te
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 23 เปรียบเทียบ
ubst
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 24 เปรียบเทียบ
bstr
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 25 เปรียบเทียบ
stre
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปที่ตำแหน่ง 26 เปรียบเทียบ
trin
กับ "substring" ไม่มีการแข่งขัน - ย้ายไปตำแหน่ง 27 เปรียบเทียบ
ring
กับ "substring" พบการแข่งขัน บันทึกตำแหน่ง 27.
สตริงย่อย "substring" อยู่ที่ตำแหน่ง 27 ภายในข้อความ
ตัวอย่างโค้ดในภาษา C++
ในตัวอย่างนี้ textSearch
ฟังก์ชันใช้เพื่อค้นหาตำแหน่งของสตริงย่อย "substring" ภายในข้อความ ผลลัพธ์จะเป็นเวกเตอร์ที่มีตำแหน่งเริ่มต้นของการแข่งขัน