From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- string/manacher.cpp | 51 ++++++++++++++++++++++++--------------------------- 1 file changed, 24 insertions(+), 27 deletions(-) (limited to 'string/manacher.cpp') 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 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 -- cgit v1.2.3