อัลกอริทึมการค้นหาสตริงหรือบางครั้งเรียกว่าอัลกอริทึมการจับคู่สตริงคืออัลกอริทึมที่ค้นหาส่วนของข้อความที่ตรงกับรูปแบบที่กำหนดไว้

ตัวอย่างพื้นฐานของการค้นหาสตริงคือ เมื่อรูปแบบและข้อความที่ต้องการค้นหาเป็นอาร์เรย์ขององค์ประกอบในตัวอักษร ( เซตจำกัด ) Σ โดย Σ อาจเป็นตัวอักษรในภาษาของมนุษย์ เช่น ตัวอักษรAถึงZและในแอปพลิเคชันอื่นๆ อาจใช้ตัวอักษรไบนารี (Σ = {0,1}) หรือตัวอักษรดีเอ็นเอ (Σ = {A,C,G,T}) ในชีวสารสนเทศ

ในทางปฏิบัติ วิธีการค้นหาสตริงที่เป็นไปได้อาจได้รับผลกระทบจากการเข้ารหัสสตริง โดยเฉพาะอย่างยิ่ง หากใช้การเข้ารหัสแบบความกว้างแปรผัน อาจทำให้การค้นหาอักขระตัวที่ N ช้าลง อาจต้องใช้เวลาแปรผันตามNซึ่งอาจทำให้อัลกอริทึมการค้นหาบางตัวทำงานช้าลงอย่างมาก หนึ่งในวิธีแก้ปัญหาที่เป็นไปได้หลายวิธีคือการค้นหาลำดับของหน่วยรหัสแทน แต่การทำเช่นนั้นอาจทำให้เกิดการจับคู่ที่ผิดพลาดได้ เว้นแต่การเข้ารหัสจะได้รับการออกแบบมาเป็นพิเศษเพื่อหลีกเลี่ยงปัญหานี้

การค้นหาสตริงแบบพื้นฐานที่สุดเกี่ยวข้องกับสตริงหนึ่ง (มักจะยาวมาก) ซึ่งบางครั้งเรียกว่ากองฟางและสตริงหนึ่ง (มักจะสั้นมาก) ซึ่งบางครั้งเรียกว่าเข็มเป้าหมายคือการค้นหาคำที่ตรงกับเข็มอย่างน้อยหนึ่งคำภายในกองฟาง ตัวอย่างเช่น อาจค้นหาคำว่า " to"ภายใน:

หนังสือบางเล่มควรลิ้มลอง บางเล่มควรอ่านรวดเดียวจบ และบางเล่มควรค่อยๆ เคี้ยวและย่อยให้ละเอียด 

อาจต้องการทราบคำว่า "to" ที่ปรากฏครั้งแรก ซึ่งเป็นคำที่สี่ หรืออาจต้องการทราบทุกครั้งที่มีคำว่า "to" ปรากฏ ซึ่งมีทั้งหมด 3 ครั้ง หรืออาจต้องการทราบครั้งสุดท้าย ซึ่งเป็นคำที่ห้าจากท้ายประโยค

อย่างไรก็ตาม โดยทั่วไปแล้ว มักมีการเพิ่มข้อจำกัดต่างๆ เข้ามา ตัวอย่างเช่น อาจต้องการให้คำค้นหาตรงกับคำที่ประกอบด้วยคำที่สมบูรณ์อย่างน้อยหนึ่งคำ (หรือมากกว่านั้น) ซึ่งอาจกำหนดไว้ว่า ต้อง ไม่มีตัวอักษรอื่นๆ อยู่ติดกันทั้งสองด้าน ในกรณีนั้น การค้นหาคำว่า "hew" หรือ "low" ควรล้มเหลวสำหรับประโยคตัวอย่างข้างต้น แม้ว่าจะมีคำเหล่านั้นอยู่จริงก็ตาม

อีกตัวอย่างหนึ่งที่พบได้บ่อยคือเรื่อง "การทำให้เป็นมาตรฐาน" ในหลายกรณี การค้นหาวลีเช่น "to be" ควรจะประสบความสำเร็จแม้ในสถานที่ที่มีคำอื่นแทรกอยู่ระหว่าง "to" และ "be" ก็ตาม

• มากกว่าหนึ่งพื้นที่
• อักขระ "ช่องว่าง" อื่นๆ เช่น แท็บ ช่องว่างที่ไม่เว้นวรรค การขึ้นบรรทัดใหม่ เป็นต้น
• ที่พบได้น้อยกว่าคือเครื่องหมายยัติภังค์หรือยัติภังค์อ่อน
• ในข้อความที่มีโครงสร้างแท็กหรือแม้แต่สิ่งที่มีขนาดใหญ่แต่ "อยู่ในวงเล็บ" เช่น เชิงอรรถ หมายเลขรายการ หรือเครื่องหมายอื่นๆ รูปภาพที่ฝังอยู่ และอื่นๆ ก็มีความสำคัญเช่นกัน

ระบบสัญลักษณ์หลายระบบมีตัวอักษรที่มีความหมายเหมือนกัน (อย่างน้อยก็สำหรับบางวัตถุประสงค์):

• อักษรละตินแยกความแตกต่างระหว่างตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ แต่สำหรับวัตถุประสงค์หลายอย่าง การค้นหาข้อความมักไม่จำเป็นต้องคำนึงถึงความแตกต่างนี้
• ภาษาหลายภาษามีอักษรเชื่อม (ligatures ) ซึ่งอักษรผสมตัวหนึ่งจะเทียบเท่ากับอักษรอื่นสองตัวขึ้นไป
• ระบบการเขียนหลายระบบมีการใช้เครื่องหมายเสริมเช่น เครื่องหมายเน้นเสียงหรือเครื่องหมายสระซึ่งอาจมีการใช้งานที่แตกต่างกัน หรือมีความสำคัญในการจับคู่ที่แตกต่างกันไป
• ลำดับดีเอ็นเออาจมี ส่วนที่ ไม่เข้ารหัสซึ่งอาจถูกละเลยในบางกรณี หรืออาจมีโพลีมอร์ฟิซึมที่ไม่ก่อให้เกิดการเปลี่ยนแปลงในโปรตีนที่เข้ารหัส ซึ่งอาจไม่นับเป็นความแตกต่างที่แท้จริงในบางกรณีอื่น ๆ
• บางภาษามีข้อกำหนดว่าต้องใช้ตัวอักษรหรือรูปแบบตัวอักษรที่แตกต่างกันในตอนต้น ตอนกลาง หรือตอนท้ายของคำ

สุดท้ายนี้ สำหรับสตริงที่แสดงถึงภาษาธรรมชาติ ลักษณะของภาษาเองก็จะเข้ามาเกี่ยวข้องด้วย ตัวอย่างเช่น เราอาจต้องการค้นหาคำทุกคำที่ปรากฏ แม้ว่าคำนั้นจะมีตัวสะกด คำนำหน้า หรือคำต่อท้ายที่แตกต่างกันก็ตาม

การค้นหาอีกประเภทหนึ่งที่ซับซ้อนกว่าคือ การค้นหา ด้วยนิพจน์ปกติ (Regular Expression ) ซึ่งผู้ใช้จะสร้างรูปแบบของตัวอักษรหรือสัญลักษณ์อื่นๆ และการจับคู่กับรูปแบบนั้นจะส่งผลให้การค้นหาสำเร็จ ตัวอย่างเช่น ในการค้นหาทั้งคำว่า "color" ในภาษาอังกฤษแบบอเมริกันและคำว่า "colour" ในภาษาอังกฤษแบบอังกฤษ แทนที่จะค้นหาสตริงตัวอักษรสองแบบที่แตกต่างกัน เราอาจใช้นิพจน์ปกติเช่น:

สี 

โดยที่เครื่องหมาย "?" ตามธรรมเนียมแล้วจะทำให้ตัวอักษรที่อยู่ข้างหน้า ("u") เป็นตัวเลือก

บทความนี้กล่าวถึงอัลกอริธึมสำหรับการค้นหาสตริงประเภทที่ง่ายกว่าเป็นหลัก

ปัญหาที่คล้ายกันซึ่งนำเสนอในสาขาชีวสารสนเทศและจีโนมิกส์คือการจับคู่ที่แม่นยำที่สุด (MEM) ^{[ 1 ]}เมื่อกำหนดสตริงสองสตริง MEM คือสตริงย่อยทั่วไปที่ไม่สามารถขยายไปทางซ้ายหรือขวาได้โดยไม่ทำให้เกิดความไม่ตรงกัน^{[ 2 ]}

วิธีที่ง่ายและไม่มีประสิทธิภาพในการตรวจสอบว่าสตริงหนึ่งปรากฏอยู่ภายในอีกสตริงหนึ่งที่ใด คือการตรวจสอบทีละดัชนี ขั้นแรก เราจะดูว่ามีสำเนาของสตริงที่ต้องการค้นหาอยู่ที่อักขระตัวแรกของกองข้อมูลหรือไม่ ถ้าไม่มี เราจะดูว่ามีสำเนาของสตริงที่ต้องการค้นหาอยู่ที่อักขระตัวที่สองของกองข้อมูลหรือไม่ และทำเช่นนี้ต่อไปเรื่อยๆ ในกรณีปกติ เราต้องตรวจสอบเพียงหนึ่งหรือสองตัวอักขระสำหรับแต่ละตำแหน่งที่ผิดเพื่อดูว่าเป็นตำแหน่งที่ผิด ดังนั้นในกรณีเฉลี่ย จะใช้เวลาO ( n + m ) ขั้นตอน โดยที่nคือความยาวของกองข้อมูลและmคือความยาวของสตริงที่ต้องการค้นหา แต่ในกรณีที่แย่ที่สุด การค้นหาสตริงเช่น "aaaab" ในสตริงเช่น "aaaaaaaaab" จะใช้เวลาO ( nm )

ในแนวทางนี้ การย้อนกลับ (backtracking) จะถูกหลีกเลี่ยงโดยการสร้างออโตมาตาจำกัดเชิงกำหนด (Deterministic Finite Automaton หรือ DFA) ที่รู้จักสตริงค้นหาที่จัดเก็บไว้ การสร้าง DFA นั้นมีค่าใช้จ่ายสูง—โดยปกติจะสร้างโดยใช้การสร้างเซตกำลัง —แต่ใช้งานได้รวดเร็วมาก ตัวอย่างเช่นDFAที่แสดงทางด้านขวารู้จักคำว่า "MOMMY" แนวทางนี้มักถูกนำไปใช้ในทางปฏิบัติเพื่อค้นหานิพจน์ปกติ (regular expression ) ใดๆ ก็ได้

อัลกอริทึม Knuth–Morris–PrattคำนวณDFAที่รู้จักอินพุตที่มีสตริงที่ต้องการค้นหาเป็นส่วนต่อท้าย อัลกอริทึมBoyer–Mooreเริ่มค้นหาจากท้ายสุดของสตริงที่ต้องการค้นหา ดังนั้นจึงสามารถข้ามไปข้างหน้าได้เท่ากับความยาวของสตริงที่ต้องการค้นหาในแต่ละขั้นตอน อัลกอริทึม Baeza–Yates จะติดตามว่า อักขระ j ตัวก่อนหน้า เป็นส่วนนำหน้าของสตริงที่ต้องการค้นหาหรือไม่ จึงสามารถปรับใช้กับการค้นหาสตริงแบบคลุมเครือได้อัลกอริทึม Bitapเป็นการประยุกต์ใช้แนวทางของ Baeza–Yates

อัลกอริทึมการค้นหาที่เร็วกว่าจะประมวลผลข้อความล่วงหน้า หลังจากสร้างดัชนีสตริงย่อยเช่นต้นไม้คำต่อท้ายหรืออาร์เรย์คำต่อท้ายแล้ว จะสามารถค้นหาการปรากฏของรูปแบบได้อย่างรวดเร็ว ตัวอย่างเช่น สามารถสร้างต้นไม้คำต่อท้ายได้ในเวลา และสามารถค้นหาการปรากฏทั้งหมดของรูปแบบได้ในเวลา ภายใต้สมมติฐานที่ว่าตัวอักษรมีขนาดคงที่และโหนดภายในทั้งหมดในต้นไม้คำต่อท้ายรู้ว่ามีใบใดอยู่ข้างใต้ ซึ่งสามารถทำได้โดยการเรียกใช้อัลกอริทึม DFSจากรากของต้นไม้คำต่อท้าย ${\displaystyle \Theta (n)}$${\displaystyle z}$${\displaystyle O(m)}$

วิธีการค้นหาบางวิธี เช่นการค้นหาแบบไตรแกรมมีจุดประสงค์เพื่อหาค่า "ความใกล้เคียง" ระหว่างสตริงที่ใช้ค้นหากับข้อความ มากกว่าการหาค่า "ตรงกัน/ไม่ตรงกัน" บางครั้งการค้นหาแบบนี้เรียกว่าการค้นหาแบบ "คลุมเครือ" (fuzzy search )

อัลกอริทึมต่างๆสามารถจำแนกได้ตามจำนวนรูปแบบที่แต่ละอัลกอริทึมใช้

ในชุดข้อมูลต่อไปนี้mคือความยาวของรูปแบบnคือความยาวของข้อความที่ค้นหาได้ และk = |Σ| คือขนาดของตัวอักษร

1. ^เวลาเชิงอะซิมโทติกแสดงโดยใช้สัญลักษณ์ O, Ω และ Θ

2. ^ใช้เพื่อใช้ งานฟังก์ชันการค้นหา memmemและstrstrในไลบรารีมาตรฐาน C glibc ^{[ 6 ]}และmusl ^{[ 7 ]}

3. ^สามารถขยายเพื่อรองรับการจับคู่สตริงโดยประมาณและชุดรูปแบบ (ที่อาจมีจำนวนอนันต์) ที่แสดงเป็นภาษาปกติได้

อัลกอริทึมการค้นหาสตริง Boyer–Mooreถือเป็นเกณฑ์มาตรฐานสำหรับวรรณกรรมการค้นหาสตริงเชิงปฏิบัติ^{[ 8 ]}

ในการรวบรวมข้อมูลต่อไปนี้Mคือความยาวของรูปแบบที่ยาวที่สุดmคือความยาวรวมทั้งหมดn คือความยาวของข้อความที่ค้นหาได้ และoคือจำนวนครั้งที่ปรากฏ

โดยธรรมชาติแล้ว ในกรณีนี้ รูปแบบต่างๆ ไม่สามารถแจงนับได้อย่างจำกัด โดยปกติแล้วจะใช้ไวยากรณ์ปกติหรือนิพจน์ปกติ มา แทน

วิธีการจำแนกประเภทอื่นๆ ก็เป็นไปได้เช่นกัน หนึ่งในวิธีที่พบได้บ่อยที่สุดคือการใช้การประมวลผลล่วงหน้าเป็นเกณฑ์หลัก

อีกวิธีหนึ่งจำแนกอัลกอริทึมตามกลยุทธ์การจับคู่: ^{[ 12 ]}

• จับคู่คำนำหน้าก่อน (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
• จับคู่คำต่อท้ายก่อน (Boyer–Moore และรูปแบบต่างๆ, Commentz-Walter)
• เลือกใช้ปัจจัยที่ดีที่สุดก่อน (BNDM, BOM, Set-BOM)
• กลยุทธ์อื่นๆ (แบบง่าย, แบบ Rabin–Karp, แบบเวกเตอร์)

ในการจับคู่สตริงแบบเรียลไทม์ จำเป็นต้องให้ตัวจับคู่แสดงผลการตอบกลับหลังจากอ่านอักขระแต่ละตัวของข้อความ ซึ่งระบุว่านี่คืออักขระตัวสุดท้ายของการจับคู่หรือไม่ การตอบกลับจะต้องให้ภายในเวลาคงที่ ข้อกำหนดเกี่ยวกับการประมวลผลล่วงหน้าจะแตกต่างกันไป อาจอนุญาตให้มีการประมวลผลล่วงหน้า O( m ) หลังจากอ่านรูปแบบแล้ว (แต่ก่อนการอ่านข้อความ) หรืออาจมีข้อกำหนดที่เข้มงวดกว่า โดยที่ตัวจับคู่จะต้องหยุดชั่วคราวเป็นเวลาไม่เกินค่าคงที่หลังจากอ่านอักขระใดๆ ของรูปแบบ (รวมถึงตัวสุดท้าย) สำหรับเวอร์ชันที่ผ่อนปรนกว่า หากไม่กังวลว่าเวลาในการประมวลผลล่วงหน้าและข้อกำหนดด้านหน่วยความจำจะขึ้นอยู่กับขนาดของตัวอักษร การจับคู่แบบออโตมาตอนจะให้โซลูชันแบบเรียลไทม์ Zvi Galilได้พัฒนาวิธีการเปลี่ยนอัลกอริทึมบางอย่างให้เป็นอัลกอริทึมแบบเรียลไทม์ และนำไปใช้เพื่อสร้างตัวแปรของตัวจับคู่ KMP ที่ทำงานแบบเรียลไทม์ภายใต้ข้อกำหนดที่เข้มงวด^{[ 13 ]}

ในเวอร์ชันของปัญหาการค้นหาสตริงนี้ มีสัญลักษณ์พิเศษ ø (อ่านว่า: ไม่สนใจ) ซึ่งสามารถจับคู่กับสัญลักษณ์อื่นใดก็ได้ (รวมถึง ø อีกตัว) สัญลักษณ์ที่ไม่สนใจสามารถปรากฏได้ทั้งในรูปแบบหรือในข้อความ ในปี 2545 Richard ColeและRamesh Hariharanได้เสนออัลกอริทึมสำหรับปัญหานี้ซึ่งทำงานในเวลาโดยปรับปรุงจากวิธีแก้ปัญหาในปี 2516 โดยFischerและPaterson ซึ่งมีความซับซ้อนโดยที่kคือขนาดของตัวอักษร^{[ 14 ]} CliffordและCliffordได้ เสนออัลกอริทึมอีกตัวหนึ่งซึ่งอ้างว่าง่ายกว่า^{[ 15 ]}${\displaystyle O(n\log m)}$${\displaystyle O(n\log m\log k)}$

• การจัดเรียงลำดับ
• การจับคู่กราฟ
• การจับคู่รูปแบบ
• การจับคู่รูปแบบบีบอัด
• การจับคู่ไวด์การ์ด
• การจับคู่สตริงโดยประมาณ
• การค้นหาข้อความเต็ม
• การจับคู่รูปแบบสองมิติ

• RS Boyer และ JS Moore, อัลกอริทึมการค้นหาสตริงที่รวดเร็ว , Carom. ACM 20, (10), 262–272(1977)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. RivestและClifford Stein . Introduction to Algorithms , ฉบับที่ 3. MIT Press และ McGraw-Hill, 2009. ISBN 0-262-03293-7บทที่ 32: การจับคู่สตริง, หน้า 985–1013.

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับ อัลกอริธึ มการค้นหาสตริง

• รายการลิงก์การจับคู่รูปแบบจำนวนมาก อัปเดตล่าสุด: 27/12/2551 20:18:38
• รายการอัลกอริธึมการจับคู่สตริงขนาดใหญ่ (ที่ได้รับการดูแลรักษาอย่างต่อเนื่อง)
• รายชื่ออัลกอริธึมการจับคู่สตริงของ NIST
• StringSearch – อัลกอริทึมการจับคู่รูปแบบประสิทธิภาพสูงใน Java – การใช้งานอัลกอริทึมการจับคู่สตริงหลายแบบใน Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
• StringsAndChars – การใช้งานอัลกอริธึมการจับคู่สตริงหลายแบบ (สำหรับรูปแบบเดียวและหลายรูปแบบ) ในภาษา Java
• อัลกอริทึมการจับคู่สตริงที่ตรงเป๊ะ — ภาพเคลื่อนไหวในภาษา Java คำอธิบายโดยละเอียดและการใช้งานอัลกอริทึมหลายตัวในภาษา C
• (PDF) การปรับปรุงการจับคู่สตริงโดยประมาณแบบเดี่ยวและหลายรายการเก็บถาวรเมื่อ 11 มีนาคม 2017 ที่Wayback Machine
• Kalign2: การจัดเรียงลำดับโปรตีนและนิวคลีโอไทด์หลายลำดับที่มีประสิทธิภาพสูง รองรับคุณสมบัติภายนอก
• NyoTengu – อัลกอริทึมการจับคู่รูปแบบประสิทธิภาพสูงในภาษา C – การใช้งานอัลกอริทึมการจับคู่สตริงแบบเวกเตอร์และแบบสเกลาร์ในภาษา C
• Nathaniel K. Brown และคณะ: "KeBaB: การแตกตัวตาม k-mer เพื่อค้นหา MEM ยาว" arXiv:2502.20338v3 (9 มิถุนายน 2025)