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/suffixArray.cpp | 52 ++++++++++++++++++++++++++++----------------------
 1 file changed, 29 insertions(+), 23 deletions(-)

(limited to 'string/suffixArray.cpp')

diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp
index 17a10cf..66b0ee9 100644
--- a/string/suffixArray.cpp
+++ b/string/suffixArray.cpp
@@ -1,31 +1,37 @@
-struct SuffixArray { // MAX_LG = ceil(log2(MAX_N))
-	static const int MAX_N = 100010, MAX_LG = 17;
-	pair<pair<int, int>, int> L[MAX_N];
-	int P[MAX_LG + 1][MAX_N], n, step, count;
-	int suffixArray[MAX_N], lcpArray[MAX_N]; 
+struct SuffixArray {
+	vector<pair<pair<int, int>, int>> L;
+	int n, step, count;
+	vector<vector<int>> P;
+	vector<int> SA, LCP; 
 
-	SuffixArray(const string &s) : n(s.size()) { // Laufzeit: O(n*log^2(n))
+	SuffixArray(const string& s) : n(sz(s)) {
+		SA.resize(n); LCP.resize(n); L.resize(n);
+		P.assign(ceil(log2(n)) + 1, vector<int>(n));
 		for (int i = 0; i < n; i++) P[0][i] = s[i];
-		suffixArray[0] = 0; // Falls n == 1.
-		for (step = 1, count = 1; count < n; step++, count <<= 1) {
-			for (int i = 0; i < n; i++) L[i] =
-					{{P[step-1][i], i+count < n ? P[step-1][i+count] : -1}, i};
-			sort(L, L + n);
-			for (int i = 0; i < n; i++) P[step][L[i].second] = i > 0 &&
-					L[i].first == L[i-1].first ? P[step][L[i-1].second] : i;
-		}
-		for (int i = 0; i < n; i++) suffixArray[i] = L[i].second;
-		for (int i = 1; i < n; i++)
-			lcpArray[i] = lcp(suffixArray[i - 1], suffixArray[i]);
+		for (step = 1, count = 1; count < n; step++, count *= 2) {
+			for (int i = 0; i < n; i++)
+				L[i] = {{P[step-1][i], 
+						 		 i+count < n ? P[step-1][i+count] : -1}, i};
+			sort(L.begin(), L.end());
+			for (int i = 0; i < n; i++) {
+				P[step][L[i].second] = 
+					i > 0 && L[i].first == L[i-1].first ?
+					P[step][L[i-1].second] : i;
+		}}
+		for (int i = 0; i < n; i++) SA[i] = L[i].second;
+		for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i - 1], SA[i]);
 	}
 
-	// x und y sind Indizes im String, nicht im Suffixarray.
-	int lcp(int x, int y) { // Laufzeit: O(log(n))
-		int k, ret = 0;
+	// x and y are text-indices, not SA-indices.
+	int lcp(int x, int y) {
+		int ret = 0;
 		if (x == y) return n - x;
-		for (k = step - 1; k >= 0 && x < n && y < n; k--)
-			if (P[k][x] == P[k][y])
-				x += 1 << k, y += 1 << k, ret += 1 << k;
+		for (int k = step - 1; k >= 0 && x < n && y < n; k--)
+			if (P[k][x] == P[k][y]) {
+				x += 1 << k;
+				y += 1 << k;
+				ret += 1 << k;
+			}
 		return ret;
 	}
 };
-- 
cgit v1.2.3