From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 string/z.cpp | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
 create mode 100644 string/z.cpp

(limited to 'string/z.cpp')

diff --git a/string/z.cpp b/string/z.cpp
new file mode 100644
index 0000000..dbd5ce5
--- /dev/null
+++ b/string/z.cpp
@@ -0,0 +1,15 @@
+vector<int> Z(const vector<int> &s) {
+	int n = sz(s);
+	vector<int> z(n, n);
+	int l = 0, r = 0, p, q;
+	for (int i = 1; i < n; ++i) {
+		if (i <= r && z[i - l] < r - i + 1) {
+			z[i] = z[i - l];
+		} else {
+			if (i > r) p = 0, q = i;
+			else p = r - i + 1, q = r + 1;
+			while (q < n && s[p] == s[q]) ++p, ++q;
+			z[i] = q - i, l = i, r = q - 1;
+	}}
+	return z;
+}
-- 
cgit v1.2.3