الگوریتم 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.

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}

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. 

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 

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