improve suffixArray

2 files changed, 12 insertions, 19 deletions

diff --git a/string/string.tex b/string/string.tex
index 52284d9..c36ec69 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -87,7 +87,7 @@
 \begin{algorithm}{Suffix-Array}
 \begin{methods}
 	\method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})}
-	\method{lcp}{berechnet den logest common prefix}{\log(\abs{s})}
+	\method{lcp}{berechnet den longest common prefix}{\log(\abs{s})}
 	\method{}{von \code{s[x]} und \code{s[y]}}{}
 \end{methods}
 \sourcecode{string/suffixArray.cpp}
diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp
index d584ebf..9e6960e 100644
--- a/string/suffixArray.cpp
+++ b/string/suffixArray.cpp
@@ -1,23 +1,19 @@
 struct SuffixArray {
-	int n, k, c;
+	int n;
 	vector<int> SA, LCP;
 	vector<vector<int>> P;
 
 	SuffixArray(const string& s) : n(sz(s)), SA(n), LCP(n) {
 		vector<ll> L(n);
-		P.assign(__lg(n)+2, vector<int>(n));
-		for (int i = 0; i < n; i++) P[0][i] = s[i];
+		P.assign(__lg(n - 1) + 2, vector<int>(n, 1));
+		P[0] = vector<int>(all(s));
 		iota(all(SA), 0);
-		for (k = 1, c = 1; c < n; k++, c *= 2) {
-			for (int i = 0; i < n; i++) L[i] = (ll)P[k-1][i] << 32;
-			for (int i = 0; i+c < n; i++) L[i] |= P[k-1][i+c];
-			sort(all(SA), [&](int a, int b){
-				return L[a] != L[b] ? L[a] < L[b] : a < b;
-			});
-			P[k][SA[0]] = 1;
+		for (int k = 1, c = 1; c < n; k++, c *= 2) {
+			for (int i = 0; i < n; i++) L[i] = (ll)P[k - 1][i] << 32;
+			for (int i = 0; i+c < n; i++) L[i] |= P[k - 1][i + c];
+			sort(all(SA), [&](int a, int b) {return L[a] < L[b];});
 			for (int i = 1; i < n; i++) {
-				P[k][SA[i]] = L[SA[i]] == L[SA[i-1]] ? P[k][SA[i-1]]
-				                                     : i+1;
+				P[k][SA[i]] = P[k][SA[i-1]] + (L[SA[i]] != L[SA[i-1]]);
 		}}
 		for (int i = 1; i < n; i++) LCP[i] = lcp(SA[i-1], SA[i]);
 	}
@@ -26,12 +22,9 @@ struct SuffixArray {
 	int lcp(int x, int y) {
 		int ret = 0;
 		if (x == y) return n - x;
-		for (int i = k - 1; i >= 0 && x < n && y < n; i--) {
-			if (P[i][x] == P[i][y]) {
-				x += 1 << i;
-				y += 1 << i;
-				ret += 1 << i;
-		}}
+		for (int i = sz(P) - 1; i >= 0 && max(x, y) + ret < n; i--) {
+			if (P[i][x + ret] == P[i][y + ret]) ret += 1 << i;
+		}
 		return ret;
 	}
 };