1- #Z-algorithm
1+ #Z Algorithm
22
33The Z-algorithm finds occurrences of a "word"` W `
4- within a main "text string"` T ` in linear time.
4+ within a main "text string"` T ` in linear time` O(|W| + |T|) ` .
55
66Given a string` S ` of length` n ` , the algorithm produces
7- an array,` Z ` where` Z[i] ` represents theongest substring
7+ an array,` Z ` where` Z[i] ` represents thelongest substring
88starting from` S[i] ` which is also a prefix of` S ` . Finding
99` Z ` for the string obtained by concatenating the word,` W `
1010with a nonce character, say` $ ` followed by the text,` T ` ,
1111helps with pattern matching, for if there is some index` i `
1212such that` Z[i] ` equals the pattern length, then the pattern
1313must be present at that point.
1414
15- While the` Z ` array can be computed with two nested loops, the
15+ While the` Z ` array can be computed with two nested loops in ` O(|W| * |T|) ` time , the
1616following strategy shows how to obtain it in linear time, based
1717on the idea that as we iterate over the letters in the string
1818(index` i ` from` 1 ` to` n - 1 ` ), we maintain an interval` [L, R] `
@@ -21,7 +21,42 @@ and `S[L...R]` is a prefix that is also a substring (if no such
2121interval exists, just let` L = R = - 1 ` ). For` i = 1 ` , we can
2222simply compute` L ` and` R ` by comparing` S[0...] ` to` S[1...] ` .
2323
24+ ** Example of Z array**
25+
26+ ```
27+ Index 0 1 2 3 4 5 6 7 8 9 10 11
28+ Text a a b c a a b x a a a z
29+ Z values X 1 0 0 3 1 0 0 2 2 1 0
30+ ```
31+
32+ Other examples
33+
34+ ```
35+ str = a a a a a a
36+ Z[] = x 5 4 3 2 1
37+ ```
38+
39+ ```
40+ str = a a b a a c d
41+ Z[] = x 1 0 2 1 0 0
42+ ```
43+
44+ ```
45+ str = a b a b a b a b
46+ Z[] = x 0 6 0 4 0 2 0
47+ ```
48+
49+ ** Example of Z box**
50+
51+ ![ z-box] ( https://ivanyu.me/wp-content/uploads/2014/09/zalg1.png )
52+
2453##Complexity
2554
2655- ** Time:** ` O(|W| + |T|) `
27- - ** Space:** ` O(|W|) `
56+ - ** Space:** ` O(|W|) `
57+
58+ ##References
59+
60+ - [ GeeksForGeeks] ( https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/ )
61+ - [ YouTube] ( https://www.youtube.com/watch?v=CpZh4eF8QBw&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=70 )
62+ - [ Z Algorithm by Ivan Yurchenko] ( https://ivanyu.me/blog/2013/10/15/z-algorithm/ )