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

۴۱۷ بازدید
آخرین به‌روزرسانی: ۱۹ اردیبهشت ۱۴۰۲
زمان مطالعه: ۵ دقیقه
دانلود PDF مقاله
الگوریتم ساده بهینه برای جستجوی الگو – راهنمای کاربردیالگوریتم ساده بهینه برای جستجوی الگو – راهنمای کاربردی

پیش‌تر، در مطلب «جستجوی الگو (Pattern Searching) — به زبان ساده» یک الگوریتم تطبیق رشته ساده مورد بررسی قرار گرفت. اکنون، شرایطی در نظر گرفته می‌شود که در آن، همه کاراکترهای الگو متفاوت هستند. پرسشی که در این وهله مطرح می شود این است که آیا می‌توان الگوریتم ساده ارائه شده برای جستجوی الگو را به نوعی ویرایش کرد تا برای این نوع از الگوها نیز عملکرد بهتری داشته باشد؟ اگر امکان این امر وجود دارد، چه تغییراتی باید در الگوریتم اصلی داده شود. در ادامه، الگوریتم ساده بهینه برای جستجوی الگو مورد بررسی قرار می‌گیرد و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، پایتون، C، جاوا، #C و PHP انجام می‌شود.

997696

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

در الگوریتم تطبیق رشته نایو، همیشه الگو ۱ واحد اسلاید می‌شود. هنگامی که همه کاراکترهای الگو متفاوت باشند، می‌توان الگو را بیش از ۱ واحد اسلاید کرد. در ادامه، روش انجام این کار مورد بررسی قرار می‌گیرد. هنگامی که یک عدم تطابق بعد از تطبیق پیدا کردن j اتفاق می‌افتد، اولین کاراکتر الگو با کاراکترهای تطبیق پیدا کرده با j تطبیق پیدا نمی‌کند؛ زیرا همه کاراکترهای الگو متفاوت هستند.

بنابراین، همیشه می‌توان الگو را با j و بدون از دست دادن هر شیف معتبری، اسلاید کرد. در ادامه، کد پیاده‌سازی الگوریتم نایو بهینه‌سازی شده برای جستجوی الگو ارائه شده است. شایان توجه است که منظور از اسلاید کردن، در واقع داشتن یک کشوی لغزنده فرضی است که روی کاراکترها جا به جا می‌شود.

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

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

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

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

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

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

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

Pattern found at index 4
Pattern found at index 12

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

^^

بر اساس رای ۲ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
دانلود PDF مقاله
نظر شما چیست؟

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