فرادرس
الگوریتم ساده بهینه برای جستجوی الگو — راهنمای کاربردی
۵۸ بازدید
آخرین به‌روزرسانی:
۱۹ اردیبهشت ۱۴۰۲
زمان مطالعه:
۵ دقیقه
پیش‌تر، در مطلب «جستجوی الگو (Pattern Searching) — به زبان ساده» یک الگوریتم تطبیق رشته ساده مورد بررسی قرار گرفت. اکنون، شرایطی در نظر گرفته می‌شود که در آن، همه کاراکترهای الگو متفاوت هستند. پرسشی که در این وهله مطرح می شود این است که آیا می‌توان الگوریتم ساده ارائه شده برای جستجوی الگو را به نوعی ویرایش کرد تا برای این نوع از الگوها نیز عملکرد بهتری داشته باشد؟ اگر امکان این امر وجود دارد، چه تغییراتی باید در الگوریتم اصلی داده شود. در ادامه، الگوریتم ساده بهینه برای جستجوی الگو مورد بررسی قرار می‌گیرد و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، پایتون، C، جاوا، #C و PHP انجام می‌شود.
فهرست مطالب این نوشته
الگوریتم ساده بهینه شده برای جستجوی الگو
در الگوریتم تطبیق رشته نایو، همیشه الگو ۱ واحد اسلاید می‌شود. هنگامی که همه کاراکترهای الگو متفاوت باشند، می‌توان الگو را بیش از ۱ واحد اسلاید کرد. در ادامه، روش انجام این کار مورد بررسی قرار می‌گیرد. هنگامی که یک عدم تطابق بعد از تطبیق پیدا کردن j اتفاق می‌افتد، اولین کاراکتر الگو با کاراکترهای تطبیق پیدا کرده با j تطبیق پیدا نمی‌کند؛ زیرا همه کاراکترهای الگو متفاوت هستند.
بنابراین، همیشه می‌توان الگو را با j و بدون از دست دادن هر شیف معتبری، اسلاید کرد. در ادامه، کد پیاده‌سازی الگوریتم نایو بهینه‌سازی شده برای جستجوی الگو ارائه شده است. شایان توجه است که منظور از اسلاید کردن، در واقع داشتن یک کشوی لغزنده فرضی است که روی کاراکترها جا به جا می‌شود.
الگوریتم ساده بهینه برای جستجوی الگو در ++C
/* C++ program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
#include <bits/stdc++.h>
using namespace std;
/* A modified Naive Pettern Searching
algorithn that is optimized for the
cases when all characters of pattern are different */
void search(string pat, string txt)
{
int M = pat.size();
int N = txt.size();
int i = 0;
while (i <= N - M)
{
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
cout << "Pattern found at index " << i << endl;
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
int main()
{
string txt = "ABCEABCDABCEABCD";
string pat = "ABCD";
search(pat, txt);
return 0;
}
// This code is contributed by rathbhupendra
الگوریتم ساده بهینه برای جستجوی الگو در C
/* C program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
#include<stdio.h>
#include<string.h>
/* A modified Naive Pettern Searching algorithn that is optimized
for the cases when all characters of pattern are different */
void search(char pat[], char txt[])
{
int M = strlen(pat);
int N = strlen(txt);
int i = 0;
while (i <= N - M)
{
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i+j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Pattern found at index %d \n", i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver program to test above function */
int main()
{
char txt[] = "ABCEABCDABCEABCD";
char pat[] = "ABCD";
search(pat, txt);
return 0;
}
الگوریتم ساده بهینه برای جستجوی الگو در جاوا
/* Java program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
class GFG
{
/* A modified Naive Pettern Searching
algorithn that is optimized for the
cases when all characters of pattern are different */
static void search(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
int i = 0;
while (i <= N - M)
{
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt.charAt(i + j) != pat.charAt(j))
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
System.out.println("Pattern found at index "+i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
public static void main (String[] args)
{
String txt = "ABCEABCDABCEABCD";
String pat = "ABCD";
search(pat, txt);
}
}
// This code is contributed by chandan_jnu
الگوریتم ساده بهینه برای جستجوی الگو در پایتون
# Python program for A modified Naive Pattern Searching
# algorithm that is optimized for the cases when all
# characters of pattern are different
def search(pat, txt):
M = len(pat)
N = len(txt)
i = 0
while i <= N-M:
# For current index i, check for pattern match
for j in xrange(M):
if txt[i+j] != pat[j]:
break
j += 1
if j==M: # if pat[0...M-1] = txt[i,i+1,...i+M-1]
print "Pattern found at index " + str(i)
i = i + M
elif j==0:
i = i + 1
else:
i = i+ j # slide the pattern by j
# Driver program to test the above function
txt = "ABCEABCDABCEABCD"
pat = "ABCD"
search(pat, txt)
# This code is contributed by Bhavya Jain
الگوریتم ساده بهینه برای جستجوی الگو در #C
/* C# program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
using System;
class GFG
{
/* A modified Naive Pettern Searching
algorithn that is optimized for the
cases when all characters of pattern are different */
static void search(string pat, string txt)
{
int M = pat.Length;
int N = txt.Length;
int i = 0;
while (i <= N - M)
{
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
Console.WriteLine("Pattern found at index "+i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
static void Main()
{
string txt = "ABCEABCDABCEABCD";
string pat = "ABCD";
search(pat, txt);
}
}
// This code is contributed by chandan_jnu
الگوریتم ساده بهینه برای جستجوی الگو در PHP
<?php
// PHP program for A modified Naive
// Pattern Searching algorithm that
// is optimized for the cases when all
// characters of pattern are different
/* A modified Naive Pettern Searching
algorithn that is optimized for the
cases when all characters of
pattern are different */
function search($pat, $txt)
{
$M = strlen($pat);
$N = strlen($txt);
$i = 0;
while ($i <= $N - $M)
{
$j;
/* For current index i,
check for pattern match */
for ($j = 0; $j < $M; $j++)
if ($txt[$i + $j] != $pat[$j])
break;
// if pat[0...M-1] =
// txt[i, i+1, ...i+M-1]
if ($j == $M)
{
echo("Pattern found at index $i"."\n" );
$i = $i + $M;
}
else if ($j == 0)
$i = $i + 1;
else
// slide the pattern by j
$i = $i + $j;
}
}
// Driver Code
$txt = "ABCEABCDABCEABCD";
$pat = "ABCD";
search($pat, $txt);
// This code is contributed by nitin mittal.
?>
خروجی قطعه کدهای بالا، به صورت زیر است.
Pattern found at index 4 Pattern found at index 12
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
ثبت نظر
منابع:
GeeksforGeeks
کپی شد
«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.
مطالب مرتبط
