در این مطلب، جستجوی الگو (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

جستجوی الگو (Pattern Searching)

جستجوی الگو، یک مسأله مهم در علوم کامپیوتر است. هنگامی که یک رشته در فایل «نوت‌پد» (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 بهبود می‌بخشد.

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

^^

الهام حصارکی (+)

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *