جستجوی الگو (Pattern Searching) – به زبان ساده

در این مطلب، جستجوی الگو (Pattern Searching) مورد بررسی قرار می‌گیرد و یک الگوریتم ساده برای این کار ارائه می‌شود. متن  [txt[0..n-1 و الگوی [pat[0..m-1 موجود است؛ هدف نوشتن تابع جستجویی ([]char pat[], char txt) است که همه وقوع‌های []pat در []txt را چاپ کند. می‌توان فرض کرد که n > m است. مثال‌های زیر در این راستا قابل توجه هستند.

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

جستجوی الگو، یک مسأله مهم در علوم کامپیوتر است. هنگامی که یک رشته در فایل «نوت‌پد» (Notepad)، «ورد» (Word)، مرورگر و یا «پایگاه‌داده» (Database) جستجو می‌شود از جستجوی الگو برای نمایش نتایج جستجو استفاده می‌شود.

الگوریتم ساده برای جستجوی الگو

الگو در متن به این صورت بررسی می‌شود که از آغاز متن به صورت اسلایدی (کشویی) با متن مطابقت داده می‌شود. اگر الگویی مطابق با الگوی جستجو شده در متن پیدا شد، فعالیت مجددا ادامه پیدا می‌کند تا سایر الگوها نیز یافت شوند.

الگوریتم ساده جستجوی الگو در ++C

الگوریتم ساده جستجوی الگو در C

الگوریتم ساده جستجوی الگو در جاوا

الگوریتم ساده جستجوی الگو در #C

الگوریتم ساده جستجوی الگو در PHP

الگوریتم ساده جستجوی الگو در پایتون ۳

خروجی و پیچیدگی زمانی

خروجی قطعه کدهای بالا، به صورت زیر است.

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

بهترین حالت

بهترین حالت هنگامی به وقوع می‌پیوندد که اولین کاراکتر از الگو هرگز در متن ظاهر نشود.

txt[] = "AABCCAADDEE";
pat[] = "FAA";

تعداد مقایسه ها در بهترین حالت (O(n است.

بدترین حالت

بدترین حالت الگوریتم جستجوی الگوی ساده در شرایط زیر به وقوع می‌پیوندد.

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

۱. هنگامی که همه کاراکترهای متن و الگو مشابه باشد:

txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

۲. همچنین، بدترین حالت هنگامی به وقوع می‌پیوندد که آخرین کاراکتر متفاوت باشد.

txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

تعداد مقایسه‌ها در بدترین حالت برابر با ((O(m*(n-m+1 است.

با وجود اینکه برخی از رشته‌ها دارای کاراکترهایی هستند که در زبان انگلیسی ظاهر نمی‌شود، اما این رشته‌ها ممکن است در دیگر کاربردها به وقوع بپیوندند (برای مثال، در متن‌های دودویی). الگوریتم تطبیق KMP، بدترین حالت را به (O(n بهبود می‌بخشد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

^^