1 files changed, 24 insertions, 27 deletions
diff --git a/string/manacher.cpp b/string/manacher.cpp
index 8bd58fb..a1cf2da 100644
--- a/string/manacher.cpp
+++ b/string/manacher.cpp
@@ -1,30 +1,27 @@
-char input[MAX_N];
-char s[2 * MAX_N + 1];
-int longest[2 * MAX_N + 1];
+string a, b; //a needs to be set
+vector<int> longest;
 
-void setDots() {
-  s[0] = '.';
-  int j = 1;
-  for (int i = 0; i < (int)strlen(input); i++) {
-    s[j++] = input[i];
-    s[j++] = '.';
-  }
-  s[j] = '\0';
-}
+//transformes "aa" to ".a.a." to find even length palindromes
+void init() {
+	b = string(sz(a) * 2 + 1, '.');
+	longest.assign(sz(b), 0);
+	for (int i = 0; i < sz(a); i++) {
+		b[2 * i + 1] = a[i];
+}}
 
 void manacher() {
-  int center = 0, last = 0, n = strlen(s);
-  memset(longest, 0, sizeof(longest));
-
-  for (int i = 1; i < n - 1; i++) {
-    int i2 = 2 * center - i;
-    longest[i] = (last > i) ? min(last - i, longest[i2]) : 0;
-    while (i + longest[i] + 1 < n && i - longest[i] - 1 >= 0 &&
-        s[i + longest[i] + 1] == s[i - longest[i] - 1]) longest[i]++;
-    if (i + longest[i] > last) {
-      center = i;
-      last = i + longest[i];
-    }
-  }
-  for (int i = 0; i < n; i++) longest[i] = 2 * longest[i] + 1;
-}
+	int center = 0, last = 0, n = sz(b);
+	for (int i = 1; i < n - 1; i++) {
+		int i2 = 2 * center - i;
+		longest[i] = (last > i) ? min(last - i, longest[i2]) : 0;
+		while (i + longest[i] + 1 < n && i - longest[i] - 1 >= 0 &&
+			  	 b[i + longest[i] + 1] == b[i - longest[i] - 1]) {
+			longest[i]++;
+		}
+		if (i + longest[i] > last) {
+			center = i;
+			last = i + longest[i];
+	}}
+	//convert lengths to string b (optional)
+	for (int i = 0; i < n; i++) longest[i] = 2 * longest[i] + 1;
+}
+\ No newline at end of file