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


پیشتر، در مطلب «جستجوی الگو (Pattern Searching) — به زبان ساده» یک الگوریتم تطبیق رشته ساده مورد بررسی قرار گرفت. اکنون، شرایطی در نظر گرفته میشود که در آن، همه کاراکترهای الگو متفاوت هستند. پرسشی که در این وهله مطرح می شود این است که آیا میتوان الگوریتم ساده ارائه شده برای جستجوی الگو را به نوعی ویرایش کرد تا برای این نوع از الگوها نیز عملکرد بهتری داشته باشد؟ اگر امکان این امر وجود دارد، چه تغییراتی باید در الگوریتم اصلی داده شود. در ادامه، الگوریتم ساده بهینه برای جستجوی الگو مورد بررسی قرار میگیرد و پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل ++C، پایتون، C، جاوا، #C و PHP انجام میشود.
الگوریتم ساده بهینه شده برای جستجوی الگو
در الگوریتم تطبیق رشته نایو، همیشه الگو ۱ واحد اسلاید میشود. هنگامی که همه کاراکترهای الگو متفاوت باشند، میتوان الگو را بیش از ۱ واحد اسلاید کرد. در ادامه، روش انجام این کار مورد بررسی قرار میگیرد. هنگامی که یک عدم تطابق بعد از تطبیق پیدا کردن j اتفاق میافتد، اولین کاراکتر الگو با کاراکترهای تطبیق پیدا کرده با j تطبیق پیدا نمیکند؛ زیرا همه کاراکترهای الگو متفاوت هستند.
بنابراین، همیشه میتوان الگو را با j و بدون از دست دادن هر شیف معتبری، اسلاید کرد. در ادامه، کد پیادهسازی الگوریتم نایو بهینهسازی شده برای جستجوی الگو ارائه شده است. شایان توجه است که منظور از اسلاید کردن، در واقع داشتن یک کشوی لغزنده فرضی است که روی کاراکترها جا به جا میشود.
الگوریتم ساده بهینه برای جستجوی الگو در ++C
الگوریتم ساده بهینه برای جستجوی الگو در C
الگوریتم ساده بهینه برای جستجوی الگو در جاوا
الگوریتم ساده بهینه برای جستجوی الگو در پایتون
الگوریتم ساده بهینه برای جستجوی الگو در #C
الگوریتم ساده بهینه برای جستجوی الگو در PHP
خروجی قطعه کدهای بالا، به صورت زیر است.
Pattern found at index 4 Pattern found at index 12
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^