Merge pull request TheAlgorithms#1362 from vakhokoto/z-function

deadshotsb · web-flow · commit 8bb54ca7a5b2 · 2020-07-22T23:23:05.000+05:30
z function added
diff --git a/Strings/ZFunction.java b/Strings/ZFunction.java
@@ -0,0 +1,33 @@
+// Initialisation of strings algorithm Z function
+// detailed review and proper examples can be seen on the link bewlow
+//
+// Link of algorithm review: https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
+package Strings;
+
+public class ZFunction {
+    private String string;
+
+    public ZFunction(String string){
+        this.string = string;
+    }
+
+    public int[] getArray(){
+        int length = string.length();
+        int[] z = new int[length];
+        int l = 0, r = 0;
+        for (int i=0; i<length; i++){
+            if (i > l && i <= r){
+                z[i] = Math.min(z[i - l], r - i + 1);
+            }
+            while (i + z[i] < length && string.charAt(z[i]) == string.charAt(i + z[i])){
+                z[i]++;
+            }
+            if (i + z[i] > r){
+                l = i;
+                r = i + z[i] - 1;
+            }
+        }
+
+        return z;
+    }
+}
