الگوریتم Z (جستجوی الگو با زمان خطی) – راهنمای کاربردی
در این مطلب، الگوریتم Z یا Z Algorithm که یک «الگوریتم جستجوی الگو» (Pattern Searching Algorithm) با زمان خطی است مورد بررسی قرار میگیرد و پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سیشارپ» (#C) انجام میشود. الگوریتم Z، همه وقوعهای یک الگو در متن را در یک زمان خطی پیدا میکند. اگر طول متن n و طول الگو m باشد، کل زمان گرفته شده O(m + n) است و در واقع، پیچیدگی زمانی و فضایی، خطی محسوب میشود. اکنون، میتوان مشاهده کرد که هم پیچیدگی زمانی و هم پیچیدگی فضایی مشابه الگوریتم KMP است؛ اما درک الگوریتم KMP سادهتر است. در این الگوریتم، یک آرایه Z ساخته میشود.
آرایه 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
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
^^