در این مطلب، الگوریتم 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 در هر نقطه‌ای مشابه با طول الگو باشد، الگو در آن نقطه نمایش داده می‌شود. مثال زیر در این راستا قابل توجه است.

The concatenated string is = "aab$baabaa"

Z array for above concatenated string is {x, 1, 0, 0, 0, 
                                          3, 1, 0, 2, 1}.
Since length of pattern is 3, the value 3 in Z array 
indicates 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

// A C++ program that implements Z algorithm for pattern searching 
#include<iostream> 
using namespace std; 
  
void getZarr(string str, int Z[]); 
  
// prints all occurrences of pattern in text using Z algo 
void search(string text, string pattern) 
{ 
    // Create concatenated string "P$T" 
    string concat = pattern + "$" + text; 
    int l = concat.length(); 
  
    // Construct Z array 
    int Z[l]; 
    getZarr(concat, Z); 
  
    // now looping through Z array for matching condition 
    for (int i = 0; i < l; ++i) 
    { 
        // if Z[i] (matched region) is equal to pattern 
        // length we got the pattern 
        if (Z[i] == pattern.length()) 
            cout << "Pattern found at index "
                << i - pattern.length() -1 << endl; 
    } 
} 
  
// Fills Z array for given string str[] 
void getZarr(string str, int Z[]) 
{ 
    int n = str.length(); 
    int L, R, k; 
  
    // [L,R] make a window which matches with prefix of s 
    L = R = 0; 
    for (int i = 1; i < n; ++i) 
    { 
        // if i>R nothing matches so we will calculate. 
        // Z[i] using naive way. 
        if (i > R) 
        { 
            L = R = i; 
  
            // R-L = 0 in starting, so it will start 
            // checking from 0'th index. For example, 
            // for "ababab" and i = 1, the value of R 
            // remains 0 and Z[i] becomes 0. For string 
            // "aaaaaa" and i = 1, Z[i] and R become 5 
            while (R<n && str[R-L] == str[R]) 
                R++; 
            Z[i] = R-L; 
            R--; 
        } 
        else
        { 
            // k = i-L so k corresponds to number which 
            // matches in [L,R] interval. 
            k = i-L; 
  
            // if Z[k] is less than remaining interval 
            // then Z[i] will be equal to Z[k]. 
            // For example, str = "ababab", i = 3, R = 5 
            // and L = 2 
            if (Z[k] < R-i+1) 
                Z[i] = Z[k]; 
  
            // For example str = "aaaaaa" and i = 2, R is 5, 
            // L is 0 
            else
            { 
                // else start from R and check manually 
                L = i; 
                while (R<n && str[R-L] == str[R]) 
                    R++; 
                Z[i] = R-L; 
                R--; 
            } 
        } 
    } 
} 
  
// Driver program 
int main() 
{ 
    string text = "GEEKS FOR GEEKS"; 
    string pattern = "GEEK"; 
    search(text, pattern); 
    return 0; 
}

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

// A Java program that implements Z algorithm for pattern 
// searching 
class GFG {  
  
    //  prints all occurrences of pattern in text using 
    // Z algo 
    public static void search(String text, String pattern) 
    { 
  
        // Create concatenated string "P$T" 
        String concat = pattern + "$" + text; 
  
        int l = concat.length(); 
  
        int Z[] = new int[l]; 
  
        // Construct Z array 
        getZarr(concat, Z); 
  
        // now looping through Z array for matching condition 
        for(int i = 0; i < l; ++i){ 
  
            // if Z[i] (matched region) is equal to pattern 
            // length we got the pattern 
  
            if(Z[i] == pattern.length()){ 
                System.out.println("Pattern found at index "
                              + (i - pattern.length() - 1)); 
            } 
        } 
    } 
  
    // Fills Z array for given string str[] 
    private static void getZarr(String str, int[] Z) { 
  
        int n = str.length(); 
          
        // [L,R] make a window which matches with  
        // prefix of s 
        int L = 0, R = 0; 
  
        for(int i = 1; i < n; ++i) { 
  
            // if i>R nothing matches so we will calculate. 
            // Z[i] using naive way. 
            if(i > R){ 
  
                L = R = i; 
  
                // R-L = 0 in starting, so it will start 
                // checking from 0'th index. For example, 
                // for "ababab" and i = 1, the value of R 
                // remains 0 and Z[i] becomes 0. For string 
                // "aaaaaa" and i = 1, Z[i] and R become 5 
  
                while(R < n && str.charAt(R - L) == str.charAt(R)) 
                    R++; 
                  
                Z[i] = R - L; 
                R--; 
  
            } 
            else{ 
  
                // k = i-L so k corresponds to number which 
                // matches in [L,R] interval. 
                int k = i - L; 
  
                // if Z[k] is less than remaining interval 
                // then Z[i] will be equal to Z[k]. 
                // For example, str = "ababab", i = 3, R = 5 
                // and L = 2 
                if(Z[k] < R - i + 1) 
                    Z[i] = Z[k]; 
  
                // For example str = "aaaaaa" and i = 2, R is 5, 
                // L is 0 
                else{ 
  
  
                // else start from R and check manually 
                    L = i; 
                    while(R < n && str.charAt(R - L) == str.charAt(R)) 
                        R++; 
                      
                    Z[i] = R - L; 
                    R--; 
                } 
            } 
        } 
    } 
      
    // Driver program 
    public static void main(String[] args)  
    { 
        String text = "GEEKS FOR GEEKS"; 
        String pattern = "GEEK"; 
  
        search(text, pattern); 
    } 
} 
  
// This code is contributed by PavanKoli. 

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

# Python3 program that implements Z algorithm 
# for pattern searching 
  
# Fills Z array for given string str[] 
def getZarr(string, z): 
    n = len(string) 
  
    # [L,R] make a window which matches 
    # with prefix of s 
    l, r, k = 0, 0, 0
    for i in range(1, n): 
  
        # if i>R nothing matches so we will calculate. 
        # Z[i] using naive way. 
        if i > r: 
            l, r = i, i 
  
            # R-L = 0 in starting, so it will start 
            # checking from 0'th index. For example, 
            # for "ababab" and i = 1, the value of R 
            # remains 0 and Z[i] becomes 0. For string 
            # "aaaaaa" and i = 1, Z[i] and R become 5 
            while r < n and string[r - l] == string[r]: 
                r += 1
            z[i] = r - l 
            r -= 1
        else: 
  
            # k = i-L so k corresponds to number which 
            # matches in [L,R] interval. 
            k = i - l 
  
            # if Z[k] is less than remaining interval 
            # then Z[i] will be equal to Z[k]. 
            # For example, str = "ababab", i = 3, R = 5 
            # and L = 2 
            if z[k] < r - i + 1: 
                z[i] = z[k] 
  
            # For example str = "aaaaaa" and i = 2,  
            # R is 5, L is 0 
            else: 
  
                # else start from R and check manually 
                l = i 
                while r < n and string[r - l] == string[r]: 
                    r += 1
                z[i] = r - l 
                r -= 1
  
# prints all occurrences of pattern  
# in text using Z algo 
def search(text, pattern): 
  
    # Create concatenated string "P$T" 
    concat = pattern + "$" + text 
    l = len(concat) 
  
    # Construct Z array 
    z = [0] * l 
    getZarr(concat, z) 
  
    # now looping through Z array for matching condition 
    for i in range(l): 
  
        # if Z[i] (matched region) is equal to pattern 
        # length we got the pattern 
        if z[i] == len(pattern): 
            print("Pattern found at index",  
                      i - len(pattern) - 1) 
  
# Driver Code 
if __name__ == "__main__": 
    text = "GEEKS FOR GEEKS"
    pattern = "GEEK"
    search(text, pattern) 
  
# This code is conributed by 
# sanjeev2552 

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

// A C# program that implements Z  
// algorithm for pattern searching  
using System; 
  
class GFG 
{ 
  
// prints all occurrences of  
// pattern in text using Z algo  
public static void search(string text, 
                          string pattern) 
{ 
  
    // Create concatenated string "P$T"  
    string concat = pattern + "$" + text; 
  
    int l = concat.Length; 
  
    int[] Z = new int[l]; 
  
    // Construct Z array  
    getZarr(concat, Z); 
  
    // now looping through Z array 
    // for matching condition  
    for (int i = 0; i < l; ++i) 
    { 
  
        // if Z[i] (matched region) is equal  
        // to pattern length we got the pattern  
  
        if (Z[i] == pattern.Length) 
        { 
            Console.WriteLine("Pattern found at index " +  
                             (i - pattern.Length - 1)); 
        } 
    } 
} 
  
// Fills Z array for given string str[]  
private static void getZarr(string str, 
                            int[] Z) 
{ 
  
    int n = str.Length; 
  
    // [L,R] make a window which  
    // matches with prefix of s  
    int L = 0, R = 0; 
  
    for (int i = 1; i < n; ++i) 
    { 
  
        // if i>R nothing matches so we will  
        // calculate. Z[i] using naive way.  
        if (i > R) 
        { 
            L = R = i; 
  
            // R-L = 0 in starting, so it will start  
            // checking from 0'th index. For example,  
            // for "ababab" and i = 1, the value of R  
            // remains 0 and Z[i] becomes 0. For string  
            // "aaaaaa" and i = 1, Z[i] and R become 5  
            while (R < n && str[R - L] == str[R]) 
            { 
                R++; 
            } 
  
            Z[i] = R - L; 
            R--; 
  
        } 
        else
        { 
  
            // k = i-L so k corresponds to number  
            // which matches in [L,R] interval.  
            int k = i - L; 
  
            // if Z[k] is less than remaining interval  
            // then Z[i] will be equal to Z[k].  
            // For example, str = "ababab", i = 3,  
            // R = 5 and L = 2  
            if (Z[k] < R - i + 1) 
            { 
                Z[i] = Z[k]; 
            } 
  
            // For example str = "aaaaaa" and  
            // i = 2, R is 5, L is 0  
            else
            { 
  
  
                // else start from R and  
                // check manually  
                L = i; 
                while (R < n && str[R - L] == str[R]) 
                { 
                    R++; 
                } 
  
                Z[i] = R - L; 
                R--; 
            } 
        } 
    } 
} 
  
// Driver Code  
public static void Main(string[] args) 
{ 
    string text = "GEEKS FOR GEEKS"; 
    string pattern = "GEEK"; 
  
    search(text, pattern); 
} 
} 
  
// This code is contributed by Shrikant13 

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

Pattern found at index 0
Pattern found at index 10

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

^^

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

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر