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

۹۵۸ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
جستجوی الگو (Pattern Searching) — به زبان ساده

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

997696
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

1// C++ program for Naive Pattern  
2// Searching algorithm 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6void search(char* pat, char* txt) 
7{ 
8    int M = strlen(pat); 
9    int N = strlen(txt); 
10  
11    /* A loop to slide pat[] one by one */
12    for (int i = 0; i <= N - M; i++) { 
13        int j; 
14  
15        /* For current index i, check for pattern match */
16        for (j = 0; j < M; j++) 
17            if (txt[i + j] != pat[j]) 
18                break; 
19  
20        if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
21            cout << "Pattern found at index "
22                 << i << endl; 
23    } 
24} 
25  
26// Driver Code 
27int main() 
28{ 
29    char txt[] = "AABAACAADAABAAABAA"; 
30    char pat[] = "AABA"; 
31    search(pat, txt); 
32    return 0; 
33} 
34  
35// This code is contributed  
36// by Akanksha Rai

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

1// C program for Naive Pattern Searching algorithm 
2#include <stdio.h> 
3#include <string.h> 
4  
5void search(char* pat, char* txt) 
6{ 
7    int M = strlen(pat); 
8    int N = strlen(txt); 
9  
10    /* A loop to slide pat[] one by one */
11    for (int i = 0; i <= N - M; i++) { 
12        int j; 
13  
14        /* For current index i, check for pattern match */
15        for (j = 0; j < M; j++) 
16            if (txt[i + j] != pat[j]) 
17                break; 
18  
19        if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
20            printf("Pattern found at index %d \n", i); 
21    } 
22} 
23  
24/* Driver program to test above function */
25int main() 
26{ 
27    char txt[] = "AABAACAADAABAAABAA"; 
28    char pat[] = "AABA"; 
29    search(pat, txt); 
30    return 0; 
31} 

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

1// Java program for Naive Pattern Searching 
2public class NaiveSearch { 
3  
4    public static void search(String txt, String pat) 
5    { 
6        int M = pat.length(); 
7        int N = txt.length(); 
8  
9        /* A loop to slide pat one by one */
10        for (int i = 0; i <= N - M; i++) { 
11  
12            int j; 
13  
14            /* For current index i, check for pattern  
15              match */
16            for (j = 0; j < M; j++) 
17                if (txt.charAt(i + j) != pat.charAt(j)) 
18                    break; 
19  
20            if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
21                System.out.println("Pattern found at index " + i); 
22        } 
23    } 
24  
25    public static void main(String[] args) 
26    { 
27        String txt = "AABAACAADAABAAABAA"; 
28        String pat = "AABA"; 
29        search(txt, pat); 
30    } 
31} 
32// This code is contributed by Harikishore

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

1// C# program for Naive Pattern Searching 
2using System; 
3  
4class GFG 
5{ 
6      
7    public static void search(String txt, String pat) 
8    { 
9        int M = pat.Length; 
10        int N = txt.Length; 
11  
12        /* A loop to slide pat one by one */
13        for (int i = 0; i <= N - M; i++) 
14        { 
15            int j; 
16  
17            /* For current index i, check for pattern  
18            match */
19            for (j = 0; j < M; j++) 
20                if (txt[i + j] != pat[j]) 
21                    break; 
22  
23            // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
24            if (j == M)  
25                Console.WriteLine("Pattern found at index " + i); 
26        } 
27    } 
28  
29    // Driver code 
30    public static void Main() 
31    { 
32        String txt = "AABAACAADAABAAABAA"; 
33        String pat = "AABA"; 
34        search(txt, pat); 
35    } 
36} 
37// This code is Contributed by Sam007

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

1<?php 
2// PHP program for Naive Pattern 
3// Searching algorithm 
4  
5function search($pat, $txt) 
6{ 
7    $M = strlen($pat); 
8    $N = strlen($txt); 
9  
10    // A loop to slide pat[]  
11    // one by one  
12    for ($i = 0; $i <= $N - $M; $i++) 
13    { 
14  
15        // For current index i,  
16        // check for pattern match  
17        for ($j = 0; $j < $M; $j++) 
18            if ($txt[$i + $j] != $pat[$j]) 
19                break; 
20  
21        // if pat[0...M-1] =  
22        // txt[i, i+1, ...i+M-1] 
23        if ($j == $M)  
24            echo "Pattern found at index ", $i."\n"; 
25    } 
26} 
27  
28    // Driver Code 
29    $txt = "AABAACAADAABAAABAA"; 
30    $pat = "AABA"; 
31    search($pat, $txt); 
32      
33// This code is contributed by Sam007 
34?>

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

1# Python3 program for Naive Pattern 
2# Searching algorithm 
3def search(pat, txt): 
4    M = len(pat) 
5    N = len(txt) 
6  
7    # A loop to slide pat[] one by one */ 
8    for i in range(N - M + 1): 
9        j = 0
10          
11        # For current index i, check  
12        # for pattern match */ 
13        for j in range(0, M): 
14            if (txt[i + j] != pat[j]): 
15                break
16  
17        if (j == M - 1):  
18            print("Pattern found at index ", i) 
19  
20# Driver Code 
21if __name__ == '__main__': 
22    txt = "AABAACAADAABAAABAA"
23    pat = "AABA"
24    search(pat, txt) 
25  
26# This code is contributed  
27# by PrinciRaj1992

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

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

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 بهبود می‌بخشد.

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

^^

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

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