همونطور که خودت گفتی این الگوریتم می بینه که رشته ی $b$ در رشته ی $a$ هست یا نه.

برای فهمیدن این الگوریتم های رشته (مثل Z algorithm و KMP و حتّی Hash) یا یک معلّمی باید داشته باشی که خیلی خوب بتونه بهت توضیح بده یا از شبیه سازی های گرافیکی که ساخته شده باید متوجّه طرز کار الگوریتم بشی، از خوندن متن توی ویکیپدیا و سایت های دیگه و حتّی خوندن شبه کد های ملّت معمولاً راحت آدم به نتیجه نمی رسه.

این شبیه سازها الگوریتم را روی یک مثال برات اجرا می کنن و می تونی بفهمی که چطور الگوریتم اجرا می شه که کدش رو بزنی.

شبیه سازی زیر، هم الگوریتم ساده تطابق رشته، هم KMP و هم الگوریتم Boyer-Moore را قرار داده که با انتخاب هر کدوم می تونی مثال اجرای الگوریتم را مشاهده کنی:

http://whocouldthat.be/visualizing-string-matching/

فرض کن دو رشته الفبا بهت داده باشند (یکی بزرگتر به اسم a و یکی کوتاهتر به اسم b) و بخواهی چک کنی آیا b یک جایی داخل a قرار داره یا نه، به عبارت دیگه آیا b زیررشته‌ای از a هست یا نه

مثلا اگر a برابر HelloWorld باشه و b برابر lloW جواب بله هست و جایگاه قرارگیری b از حرف سوم a شروع میشه. ولی اگر b برابر Word باشه جواب خیر هست.

میخواهیم یک الگوریتم برای این کار بنویسیم. فرض کن طول a برابر m حرف و طول b برابر n حرف باشه. یک راه حل ساده این هست که با شروع از هر حرف a چک کنیم که آیا b در اون نقطه قرار داره یا نه. این طوری لازم هست از هر یک از m حرف a شروع کنیم و حداکثر n حرف جلو بریم و ببینیم که b آیا اونجا هست یا نه، که زمان اجراش متناسب با $m\times n$ خواهد بود. مثلا اگر a یک رشته‌ی ۱۰۰۰ حرفی و b یک رشته‌ی ۱۰۰ حرفی باشه این کار میتونه تا ۱۰۰۰۰۰ گام طول بکشه

اما الگوریتم KMP این کار رو زمانی متناسب با n گام کاهش میده (در واقع زمان اجرا $O(n)$ خواهد بود). روال کار به این صورت هست:

فرض کن از حرف i ام از a میخوای شروع کنی و ببینی b اونجا هست یا نه. اگر همون حرف i ام با حرف اول b متفاوت بود میفهمی b اونجا نیست و سریع میری سراغ حرف بعد. یعنی برای یک حرف از a فقط یک هزینه دادی. هزینه اضافه رو وقتی میدی که مثلا از حرف i ام از a تعداد زیادی حرف، مثلا j تا حرف بری جلو و همه چیز درست به نظر برسه و اون آخر کار یک حرف با یکی از حرفهای آخر b متفاوت باشه، یک عالمه هزینه بدون هیچی!

چطور اینو حل کنیم؟ برای یک لحظه فرض کن توی b هیچ حرف تکراری وجود نداشته باشه. اون موقع اگر حرف i ام تا حرف $i+j-1$ ام از a با حرفهای اول تا j ام از b یکسان باشند و حرف بعدی متفاوت باشه، به نظرت باید چیکار کنیم؟ بریم سراغ حرف $i+1$ ام از a و چک کنیم آیا b اونجا هست یا نه؟ جواب منفیه. وقتی b حرف تکراری نداره و حرف i ام از a با حرف اول b یکسان بوده، این به این معنی هست که دیگه هیچ کدوم از حرفهای i+1 تا $i+j-1$ از a نمیتونن با حرف اول b یکسان باشند. یعنی کافیه یک جهش بزرگ داشته باشیم و با شروع از حرف $i+j$ از a چک کنیم آیا b اونجا هست یا نه. یعنی همه هزینه اضافی که کردیم رو با اون جهش جبران کردیم! هوراااا!

خب اگر b حرف تکراری داشت چطور؟ بازهم وضعمون خوبه . مثلا فکر کن حرف اول b دیگه تکرار نشده باشه. مثلا اگر b برابر hello باشه حرف h فقط حرف اولشه. بازهم به همون روش میتونیم عمل کنیم، چون اگر تا j تا حرف یکی شده باشند دیگه هیچ کدوم از حرفهای دوم تا j ام برابر حرف اول b نیست. پس بازم میتونیم j تا حرف بپریم.

حالا اگر حرف اول b بازهم داخل b تکرار شده بود چی؟ مثلا اگه b برابر baabaa باشه. اون موقع اگر مثلا تا حرف پنجم b برابر حرفهای i تا $i+4$ از a شده باشه و حرف ششم فرق داشت، باید چیکار کنیم؟ باید نگاه کنیم کدوم قسمت از b میتونه یک شروع دوباره باشه. اینجا تنها حالت شروع دوباره از حرف چهارم b هست که الگویی مشابه اول b داره. یعنی میتونیم با یک جهش ۳ حرفی، i رو سه واحد اضافه کنیم. حالا میدونی حسنش چیه؟ این که قبلا حرفهای چهارم و پنجم b رو (که عین حرفهای اول و دومش هستند) با حرفهای مرتبط از a چک کرده بودیم و دوباره لازم نیست چکشون کنیم. متوجه شدی؟

در واقع کافیه یک پیش پردازش روی b بکنیم: برای هر حرف j از b ببینیم حداکثر چند حرف از ابتدای b دقیقا معادل همان تعداد حرف در b با انتهای حرف j ام هستند. بعد با استفاده از همین پیش پردازش اندازه جهش ها رو مشخص کنیم تا پردازش اضافی نکنیم.

ببخشید طولانی شد، ولی واقعا ساده هست. روش دقیقش رو میتونی اینجا ببینی

موفق باشی