الگوریتم جستجوی رشته
الگوریتم‌های جستجوی رشته (و یا تطبیق رشته‌ها) به رده‌ی مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود. در این گونه از الگوریتم‌ها، مسئله‌ی اصلی پیدا کردن مکان‌های تکرار یک یا چند الگوی مورد جستجو (Pattern) در یک رشته‌ی بزرگ‌ (Text) است.
در این مثال، رشته‌ها از کنار هم گذاشتن تعدادی کاراکتر متعلق به یک مجموعه‌ی متناهی به نام الفبا (formula_1) ساخته می‌شوند. formula_1 می‌تواند حروف الفبای معمولی (از A تا Z)، الفبای دودویی (formula_3) یا الفبای DNA (formula_4) باشد که بسته به محل و کاربرد مسئله، تعیین می‌شود. در هر حالت از محیط اجرای الگوریتم و شرایط مسئله، باید این شرایط را به خوبی بررسی کرد و بهترین الگوریتم را برای پیاده‌سازی و استفاده برگزید. به عنوان مثال، ممکن است حالات زیر بر محیط مسئله حاکم باشد: برای گرفتن بهترین کارایی در هر یک از این شرایط، باید الگوریتم مشخصی را انتخاب کرد.
همچنین در نوعی از این مسئله، رشته‌های Pattern به صورت یک عبارت منظم داده می‌شوند، و باید جایگاه تمام زیررشته‌هایی که با آن عبارت منظم مطابق هستند به عنوان خروجی برگردانده‌شود. الگوریتم‌های جستجوی رشته به صورت کلی به سه دسته‌ی زیر تقسیم می‌شوند: در جدول زیر، چند الگوریتم معروف ذکر شده و از نظر مرتبه‌ی زمانی و حافظه با هم مقایسه شده‌اند. (formula_5 طول الگو (Pattern)، formula_6 طول رشته متن (Text) و formula_7 برابر با تعداد حروف الفبا است)
در این نوع از الگوریتم‌ها، استراتژی‌ها و ایده‌های متنوعی برای تطابق الگوهای ورودی (که به شکل عبارت منظم یا زبان منظم داده می‌شوند) به کار گرفته می‌شود.
آسان‌ترین و ناکارآمدترین راه برای آن‌که یک رشته و مکان آن را در یک متن پیدا کنیم، امتحان کردن یک به یک همه‌ی مکان‌هایی که آن رشته می‌تواند قرار بگیرد است. یعنی یک اشاره‌گر را به عنوان ابتدای الگو، روی متن جلو می‌بریم و بررسی می‌کنیم که آیا این اشاره‌گر، می‌تواند ابتدای یک تکرار از الگو در متن باشد یا خیر. برای این‌کار، کاراکترهای بعد از اشاره‌گر را دانه‌به‌دانه با الگو مقایسه می‌کنیم؛ در صورت عدم انطباق یکی از آن کاراکتر‌ها، مشخص می‌شود که اشاره‌گر در مکان فعلی نمی‌تواند نمایان‌گر یک تکرار برای رشته باشد، پس اشاره‌گر را یک واحد به جلو می‌بریم. و در صورتی تا انتهای مقایسه، هیچ تناقضی وجود نداشت، به این معنی است که اشاره‌گر به یک تکرار از الگو در متن اشاره می‌کند.
شبه‌کد جستجوی رشته‌ی ساده‌لوحانه: procedure NaiveStringMatcher (T,P) begin end
این الگوریتم از مرتبه زمانی formula_8 است (فرض می‌کنیم که در این شبه‌کد، عمل مقایسه‌ی زیررشته‌ها به صورت کاراکتر به کاراکتر انجام خواهد شد).
در این روش، ابتدا یک پذیرنده متناهی معین می‌سازیم که رشته‌هایی که حاوی الگوی مورد جستجوی ما هستند را بپذیرد؛ به این ترتیب که ابتدا یک زنجیره از State ها قرار می‌دهیم، که هر State نماینده‌ی یک مکان از الگو است (که تا آن‌جا روی الگو پیش رفته‌ایم). در واقع هر State نمایانگر یک پیشوند از الگو است. به غیر از یال‌های رو به جلو که با کاراکتر‌های متناظر الگو Label گذاری شده‌اند، هر State به‌ازای هر کاراکتر دیگر، به State ای قبل از خودش می‌رود. مثلاً State نماینده‌ی پیشوند formula_9، با یال formula_10 به State نماینده‌ی پیشوند formula_11 می‌رود، اگر و تنها اگر formula_11 بزرگ‌ترین پیشوندی از الگو باشد که برای formula_13 پسوند است. همچنین رأس انتهایی متناظر با آخرین کاراکتر الگو، رأس پذیرش است.
با خواندن کاراکتر از رشته متن و حرکت روی این DFA، هر بار که به State پذیرش برسیم، یک تکرار از الگو را در متن پیدا کرده‌ایم. همچنین با تعمیم این روش، می‌توان الگوریتمی را برای جست‌وجوی عبارت‌های منظم در متن طراحی کرد.
البته هزینه ساخت چنین پذیرنده‌ای زیاد است (در صورت استفاده از ایده‌ی الگوریتم KMP، می‌توان با زمان formula_14 این پذیرنده را ساخت) اما استفاده از آن سریع است.
DFA شکل زیر برای تشخیص دادن واژه‌ی MOMMY استفاده شده‌است:
این الگوریتم‌های جستجو متن را پیش‌پردازش می‌کنند؛ بعد از ساختن زیررشته اندیسی (برای مثال درخت پسوندی یا آرایه پسوندی)، تعداد بارهایی که الگوی مورد جستجو در متن اتفاق افتاده‌است، به سرعت مشخص می‌شود؛ برای مثال یک درخت پسوندی را می‌توان در formula_15 ساخت و همه‌ی z رخ‌داد الگوی مورد نظر در متن را می‌توان در formula_16 پیدا کرد. این کار به سادگی با استفاده از یک بار جست‌و‌جوی عمق اول روی درخت پسوندی انجام می‌شود.