بهبود ورودی (علم رایانه)
تطبیق رشته > الگوریتم هورسپول

به عنوان نمایشی از افزایش ورودی در تطبیق رشته‌ها، باید یک نسخه ساده شده از الگوریتم بویر مور، الگوریتم هورسپول Horspool را بررسی کرد. الگوریتم از نویسه n ام متن m شروع می‌شود و کاراکترها را با هم مقایسه می‌کند. بیایید این کاراکتر را x بنامیم. ۴ مورد احتمالی وجود دارد که در آینده چه اتفاقی می‌افتد.
مورد ۱: اولین مورد ممکن این است که کاراکتر x در کلید نباشد. اگر این اتفاق بیفتد، کل کلید را می‌توان به طول کلید تغییر داد.
مورد ۲: دومین مورد ممکن این است که کاراکتر x کاراکتر فعلی نیست، اما x در کلید است. اگر این اتفاق بیفتد، کلید برای تراز کردن سمت راست‌ترین نویسه x جابجا می‌شود.
مورد ۳: حالت سوم ممکن است این باشد که کاراکتر x با آخرین کاراکتر کلید مطابقت داشته باشد اما سایر کاراکترها کاملاً با کلید مطابقت نداشته باشند و x دوباره در کلید رخ ندهد. اگر این اتفاق بیفتد، کل کلید را می‌توان به طول کلید تغییر داد.
مورد ۴: چهارمین و آخرین مورد ممکن این است که کاراکتر x با کلید مطابقت دارد اما سایر کاراکترها به‌طور کامل با کلید مطابقت ندارند و x دوباره در کلید رخ می‌دهد. اگر این اتفاق بیفتد، کلید برای تراز کردن سمت راست‌ترین رخداد در صورت نویسه x جابجا می‌شود.
این ممکن است به نظر کارآمدتر از الگوریتم brute-force نباشد زیرا باید همه کاراکترها را در هر چک بررسی کند. به هر حال، این چنین نیست. الگوریتم Horspool از یک جدول تغییر برای ذخیره تعداد کاراکترهایی استفاده می‌کند که الگوریتم در صورت اجرا با یک کاراکتر خاص باید تغییر دهد. ورودی در یک جدول با هر کاراکتر ممکنی که می‌توان در متن با آن روبرو شد از قبل محاسبه می‌شود. اندازه شیفت با دو گزینه محاسبه می‌شود: یکی، اگر کاراکتر در کلید نیست، اندازه شیفت n است، طول کلید. یا دو، اگر کاراکتر در کلید ظاهر می‌شود، مقدار تغییر آن فاصله از سمت راست‌ترین نویسه در اولین n -1 کاراکتر در کلید است. به الگوریتم مولد جدول shift کلید و الفبای کاراکترهای احتمالی داده می‌شود که می‌توانند در رشته (K[0... n -1]) به عنوان ورودی ظاهر شوند و جدول shift (T[0... s ) را برمی‌گرداند. -۱]). کد شبه برای تولیدکننده جدول شیفت و نمونه ای از جدول شیفت برای رشته "POTATO" در زیر نمایش داده شده‌است :
algorithm shiftTableGenerator(K[0...n-1]) is
 for i = 0 to s – 1 do
 T[i] := m
 for j := 0 to n – 2 do
 T[P[j]] := n – 1 – j
 return T
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| character x | A | B | C | ... | O | P | ... | T | ... | Z | _ |
| shift value | ۲ | ۶ | ۶ | ۶ | ۴ | ۵ | ۶ | ۱ | ۶ | ۶ | ۶ |
پس از اینکه جدول شیفت در مرحله ارتقای ورودی ساخته شد، الگوریتم کلید را ردیف کرده و اجرا را شروع می‌کند. الگوریتم تا زمانی اجرا می‌شود که زیررشته‌ای منطبق از متن m پیدا شود یا کلید با آخرین کاراکترهای متن m همپوشانی داشته باشد. اگر الگوریتم با یک جفت کاراکتر مواجه شود که مطابقت ندارند، به جدول برای مقدار تغییر کاراکتر دسترسی پیدا می‌کند و بر این اساس جابجا می‌شود. الگوریتم هورسپول کلید (K[0... n -1]) و متن (M[0... m -1]) را می‌گیرد و بسته به این که ایندکس زیررشته منطبق یا رشته «کلید یافت نشد» را خروجی می‌دهد. در نتیجه کد شبه برای الگوریتم Horspool در زیر ارائه شده‌است :
algorithm HorspoolsAlgorithm(K[0...n-1]), M [0...m-1]) is
 shiftTableGenerator(K[0...n-1])
 i:= n – 1
 while i ≤ m – 1 do
 k:= ۰
 while k ≤ m – 1 and K[n – 1 – k] = M[i – k] do
 k:= k + 1
 if k = m then
 return i – n + 1
 else
 i = i + T[M[i]]
 return “Key not found”
اگرچه ممکن است مشهود نباشد، بدترین کارایی زمان اجرا این الگوریتم O(mn) است. خوشبختانه، در متن‌هایی که تصادفی هستند، بازده زمان اجرا خطی است، O(n/m). این امر الگوریتم Horspool را که از بهبود ورودی استفاده می‌کند، در کلاس بسیار سریع‌تری نسبت به الگوریتم brute-force برای این مشکل قرار می‌دهد.