الگوریتم Z (جستجوی الگو با زمان خطی) — راهنمای کاربردی

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

در این مطلب، الگوریتم Z یا Z Algorithm که یک «الگوریتم جستجوی الگو» (Pattern Searching Algorithm) با زمان خطی است مورد بررسی قرار می‌گیرد و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) انجام می‌شود. الگوریتم Z، همه وقوع‌های یک الگو در متن را در یک زمان خطی پیدا می‌کند. اگر طول متن n و طول الگو m باشد، کل زمان گرفته شده O(m + n)‎ است و در واقع، پیچیدگی زمانی و فضایی، خطی محسوب می‌شود. اکنون، می‌توان مشاهده کرد که هم پیچیدگی زمانی و هم پیچیدگی فضایی مشابه الگوریتم KMP است؛ اما درک الگوریتم KMP ساده‌تر است. در این الگوریتم، یک آرایه Z ساخته می‌شود.

997696

آرایه Z در الگوریتم Z

برای رشته str[0..n-1]‎، آرایه Z دارای طولی مشابه با رشته است. عنصر Z[i]‎ از آرایه Z، طول بلندترین زیر رشته را با شروع از str[i]‎ ذخیره می‌کند که خود پیشوندی از str[0..n-1]‎ است.

اولین ورودی آرایه Z فاقد معنا است، زیرا رشته کامل همیشه پیشوندی از خودش محسوب می‌شود. مثال‌های زیر در این راستا، جالب توجه هستند.

Index            0   1   2   3   4   5   6   7   8   9  10  11 
Text             a   a   b   c   a   a   b   x   a   a   a   z
Z values         X   1   0   0   3   1   0   0   2   2   1   0 

str  = "aaaaaa"
Z[]  = {x, 5, 4, 3, 2, 1}

str = "aabaacd"
Z[] = {x, 1, 0, 2, 1, 0, 0}

str = "abababab"
Z[] = {x, 0, 6, 0, 4, 0, 2, 0}

آرایه Z چطور به جستجوی الگو در زمان خطی کمک می‌کند؟

ایده اصلی این روش آن است که با تمرکز روی الگو و متن، رشته «P$T» را ساخت که در آن، P الگو و $ یک کاراکتر ویژه محسوب می‌شود که نباید در الگو و متن ظاهر شود و T خود متن است.

آرایه Z را برای رشته الحاق شده باید ساخت. در آرایه Z، اگر مقدار Z در هر نقطه‌ای مشابه با طول الگو باشد، الگو در آن نقطه نمایش داده می‌شود. مثال زیر در این راستا قابل توجه است.

1The concatenated string is = "aab$baabaa"
2
3Z array for above concatenated string is {x, 1, 0, 0, 0, 
4                                          3, 1, 0, 2, 1}.
5Since length of pattern is 3, the value 3 in Z array 
6indicates presence of pattern.

روش ساخت آرایه Z

یک راهکار ساده، اجرای دو حلقه تو در تو است، حلقه بیرونی به تک تک اندیس‌ها می‌رود؛ حلقه درونی، طول بلندترین پیشوندی را پیدا می‌کند که دارای یک ویژگی خاص باشد.

این ویژگی در واقع مطابقت داشتن با زیر رشته‌ای است که از اندیس کنونی آغاز می‌شود. پیچیدگی زمانی این راهکار، از درجه O(n2)‎ است. می‌توان آرایه Z را در زمان خطی ساخت.

The idea is to maintain an interval [L, R] which is the interval with max R
such that [L,R] is prefix substring (substring which is also prefix). 

Steps for maintaining this interval are as follows – 

1) If i > R then there is no prefix substring that starts before i and 
   ends after i, so we reset L and R and compute new [L,R] by comparing 
   str[0..] to str[i..] and get Z[i] (= R-L+1).

2) If i <= R then let K = i-L, now Z[i] >= min(Z[K], R-i+1)  because 
   str[i..] matches with str[K..] for atleast R-i+1 characters (they are in
   [L,R] interval which we know is a prefix substring).     
   Now two sub cases arise – 
      a) If Z[K] < R-i+1 then there is no prefix substring starting at str[i] (otherwise Z[K] would be larger) so Z[i] = Z[K] and interval [L,R] remains same. b) If Z[K] >= R-i+1 then it is possible to extend the [L,R] interval
         thus we will set L as i and start matching from str[R]  onwards  and
         get new R then we will update interval [L,R] and calculate Z[i] (=R-L+1).

این الگوریتم، در زمان خطی اجرا می‌شود. زیرا، هرگز کاراکترهایی کمتر از R مقایسه نمی‌شوند و با تطبیق دادن، R یک واحد افزایش پیدا می‌کند؛ بنابراین، حداکثر T مقایسه وجود دارد که پیچیدگی خطی کلی را می‌سازد. در ادامه، پیاده‌سازی الگوریتم Z برای جستجوی الگو، ارائه شده است.

پیاده‌سازی الگوریتم Z در ++C

1// A C++ program that implements Z algorithm for pattern searching 
2#include<iostream> 
3using namespace std; 
4  
5void getZarr(string str, int Z[]); 
6  
7// prints all occurrences of pattern in text using Z algo 
8void search(string text, string pattern) 
9{ 
10    // Create concatenated string "P$T" 
11    string concat = pattern + "$" + text; 
12    int l = concat.length(); 
13  
14    // Construct Z array 
15    int Z[l]; 
16    getZarr(concat, Z); 
17  
18    // now looping through Z array for matching condition 
19    for (int i = 0; i < l; ++i) 
20    { 
21        // if Z[i] (matched region) is equal to pattern 
22        // length we got the pattern 
23        if (Z[i] == pattern.length()) 
24            cout << "Pattern found at index "
25                << i - pattern.length() -1 << endl; 
26    } 
27} 
28  
29// Fills Z array for given string str[] 
30void getZarr(string str, int Z[]) 
31{ 
32    int n = str.length(); 
33    int L, R, k; 
34  
35    // [L,R] make a window which matches with prefix of s 
36    L = R = 0; 
37    for (int i = 1; i < n; ++i) 
38    { 
39        // if i>R nothing matches so we will calculate. 
40        // Z[i] using naive way. 
41        if (i > R) 
42        { 
43            L = R = i; 
44  
45            // R-L = 0 in starting, so it will start 
46            // checking from 0'th index. For example, 
47            // for "ababab" and i = 1, the value of R 
48            // remains 0 and Z[i] becomes 0. For string 
49            // "aaaaaa" and i = 1, Z[i] and R become 5 
50            while (R<n && str[R-L] == str[R]) 
51                R++; 
52            Z[i] = R-L; 
53            R--; 
54        } 
55        else
56        { 
57            // k = i-L so k corresponds to number which 
58            // matches in [L,R] interval. 
59            k = i-L; 
60  
61            // if Z[k] is less than remaining interval 
62            // then Z[i] will be equal to Z[k]. 
63            // For example, str = "ababab", i = 3, R = 5 
64            // and L = 2 
65            if (Z[k] < R-i+1) 
66                Z[i] = Z[k]; 
67  
68            // For example str = "aaaaaa" and i = 2, R is 5, 
69            // L is 0 
70            else
71            { 
72                // else start from R and check manually 
73                L = i; 
74                while (R<n && str[R-L] == str[R]) 
75                    R++; 
76                Z[i] = R-L; 
77                R--; 
78            } 
79        } 
80    } 
81} 
82  
83// Driver program 
84int main() 
85{ 
86    string text = "GEEKS FOR GEEKS"; 
87    string pattern = "GEEK"; 
88    search(text, pattern); 
89    return 0; 
90}

پیاده‌سازی الگوریتم Z در جاوا

1// A Java program that implements Z algorithm for pattern 
2// searching 
3class GFG {  
4  
5    //  prints all occurrences of pattern in text using 
6    // Z algo 
7    public static void search(String text, String pattern) 
8    { 
9  
10        // Create concatenated string "P$T" 
11        String concat = pattern + "$" + text; 
12  
13        int l = concat.length(); 
14  
15        int Z[] = new int[l]; 
16  
17        // Construct Z array 
18        getZarr(concat, Z); 
19  
20        // now looping through Z array for matching condition 
21        for(int i = 0; i < l; ++i){ 
22  
23            // if Z[i] (matched region) is equal to pattern 
24            // length we got the pattern 
25  
26            if(Z[i] == pattern.length()){ 
27                System.out.println("Pattern found at index "
28                              + (i - pattern.length() - 1)); 
29            } 
30        } 
31    } 
32  
33    // Fills Z array for given string str[] 
34    private static void getZarr(String str, int[] Z) { 
35  
36        int n = str.length(); 
37          
38        // [L,R] make a window which matches with  
39        // prefix of s 
40        int L = 0, R = 0; 
41  
42        for(int i = 1; i < n; ++i) { 
43  
44            // if i>R nothing matches so we will calculate. 
45            // Z[i] using naive way. 
46            if(i > R){ 
47  
48                L = R = i; 
49  
50                // R-L = 0 in starting, so it will start 
51                // checking from 0'th index. For example, 
52                // for "ababab" and i = 1, the value of R 
53                // remains 0 and Z[i] becomes 0. For string 
54                // "aaaaaa" and i = 1, Z[i] and R become 5 
55  
56                while(R < n && str.charAt(R - L) == str.charAt(R)) 
57                    R++; 
58                  
59                Z[i] = R - L; 
60                R--; 
61  
62            } 
63            else{ 
64  
65                // k = i-L so k corresponds to number which 
66                // matches in [L,R] interval. 
67                int k = i - L; 
68  
69                // if Z[k] is less than remaining interval 
70                // then Z[i] will be equal to Z[k]. 
71                // For example, str = "ababab", i = 3, R = 5 
72                // and L = 2 
73                if(Z[k] < R - i + 1) 
74                    Z[i] = Z[k]; 
75  
76                // For example str = "aaaaaa" and i = 2, R is 5, 
77                // L is 0 
78                else{ 
79  
80  
81                // else start from R and check manually 
82                    L = i; 
83                    while(R < n && str.charAt(R - L) == str.charAt(R)) 
84                        R++; 
85                      
86                    Z[i] = R - L; 
87                    R--; 
88                } 
89            } 
90        } 
91    } 
92      
93    // Driver program 
94    public static void main(String[] args)  
95    { 
96        String text = "GEEKS FOR GEEKS"; 
97        String pattern = "GEEK"; 
98  
99        search(text, pattern); 
100    } 
101} 
102  
103// This code is contributed by PavanKoli. 

پیاده‌سازی الگوریتم Z در پایتون ۳

1# Python3 program that implements Z algorithm 
2# for pattern searching 
3  
4# Fills Z array for given string str[] 
5def getZarr(string, z): 
6    n = len(string) 
7  
8    # [L,R] make a window which matches 
9    # with prefix of s 
10    l, r, k = 0, 0, 0
11    for i in range(1, n): 
12  
13        # if i>R nothing matches so we will calculate. 
14        # Z[i] using naive way. 
15        if i > r: 
16            l, r = i, i 
17  
18            # R-L = 0 in starting, so it will start 
19            # checking from 0'th index. For example, 
20            # for "ababab" and i = 1, the value of R 
21            # remains 0 and Z[i] becomes 0. For string 
22            # "aaaaaa" and i = 1, Z[i] and R become 5 
23            while r < n and string[r - l] == string[r]: 
24                r += 1
25            z[i] = r - l 
26            r -= 1
27        else: 
28  
29            # k = i-L so k corresponds to number which 
30            # matches in [L,R] interval. 
31            k = i - l 
32  
33            # if Z[k] is less than remaining interval 
34            # then Z[i] will be equal to Z[k]. 
35            # For example, str = "ababab", i = 3, R = 5 
36            # and L = 2 
37            if z[k] < r - i + 1: 
38                z[i] = z[k] 
39  
40            # For example str = "aaaaaa" and i = 2,  
41            # R is 5, L is 0 
42            else: 
43  
44                # else start from R and check manually 
45                l = i 
46                while r < n and string[r - l] == string[r]: 
47                    r += 1
48                z[i] = r - l 
49                r -= 1
50  
51# prints all occurrences of pattern  
52# in text using Z algo 
53def search(text, pattern): 
54  
55    # Create concatenated string "P$T" 
56    concat = pattern + "$" + text 
57    l = len(concat) 
58  
59    # Construct Z array 
60    z = [0] * l 
61    getZarr(concat, z) 
62  
63    # now looping through Z array for matching condition 
64    for i in range(l): 
65  
66        # if Z[i] (matched region) is equal to pattern 
67        # length we got the pattern 
68        if z[i] == len(pattern): 
69            print("Pattern found at index",  
70                      i - len(pattern) - 1) 
71  
72# Driver Code 
73if __name__ == "__main__": 
74    text = "GEEKS FOR GEEKS"
75    pattern = "GEEK"
76    search(text, pattern) 
77  
78# This code is conributed by 
79# sanjeev2552 

پیاده‌سازی الگوریتم Z در #C

1// A C# program that implements Z  
2// algorithm for pattern searching  
3using System; 
4  
5class GFG 
6{ 
7  
8// prints all occurrences of  
9// pattern in text using Z algo  
10public static void search(string text, 
11                          string pattern) 
12{ 
13  
14    // Create concatenated string "P$T"  
15    string concat = pattern + "$" + text; 
16  
17    int l = concat.Length; 
18  
19    int[] Z = new int[l]; 
20  
21    // Construct Z array  
22    getZarr(concat, Z); 
23  
24    // now looping through Z array 
25    // for matching condition  
26    for (int i = 0; i < l; ++i) 
27    { 
28  
29        // if Z[i] (matched region) is equal  
30        // to pattern length we got the pattern  
31  
32        if (Z[i] == pattern.Length) 
33        { 
34            Console.WriteLine("Pattern found at index " +  
35                             (i - pattern.Length - 1)); 
36        } 
37    } 
38} 
39  
40// Fills Z array for given string str[]  
41private static void getZarr(string str, 
42                            int[] Z) 
43{ 
44  
45    int n = str.Length; 
46  
47    // [L,R] make a window which  
48    // matches with prefix of s  
49    int L = 0, R = 0; 
50  
51    for (int i = 1; i < n; ++i) 
52    { 
53  
54        // if i>R nothing matches so we will  
55        // calculate. Z[i] using naive way.  
56        if (i > R) 
57        { 
58            L = R = i; 
59  
60            // R-L = 0 in starting, so it will start  
61            // checking from 0'th index. For example,  
62            // for "ababab" and i = 1, the value of R  
63            // remains 0 and Z[i] becomes 0. For string  
64            // "aaaaaa" and i = 1, Z[i] and R become 5  
65            while (R < n && str[R - L] == str[R]) 
66            { 
67                R++; 
68            } 
69  
70            Z[i] = R - L; 
71            R--; 
72  
73        } 
74        else
75        { 
76  
77            // k = i-L so k corresponds to number  
78            // which matches in [L,R] interval.  
79            int k = i - L; 
80  
81            // if Z[k] is less than remaining interval  
82            // then Z[i] will be equal to Z[k].  
83            // For example, str = "ababab", i = 3,  
84            // R = 5 and L = 2  
85            if (Z[k] < R - i + 1) 
86            { 
87                Z[i] = Z[k]; 
88            } 
89  
90            // For example str = "aaaaaa" and  
91            // i = 2, R is 5, L is 0  
92            else
93            { 
94  
95  
96                // else start from R and  
97                // check manually  
98                L = i; 
99                while (R < n && str[R - L] == str[R]) 
100                { 
101                    R++; 
102                } 
103  
104                Z[i] = R - L; 
105                R--; 
106            } 
107        } 
108    } 
109} 
110  
111// Driver Code  
112public static void Main(string[] args) 
113{ 
114    string text = "GEEKS FOR GEEKS"; 
115    string pattern = "GEEK"; 
116  
117    search(text, pattern); 
118} 
119} 
120  
121// This code is contributed by Shrikant13 

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

Pattern found at index 0
Pattern found at index 10

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

^^

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

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