From 92f02961b71c82c91d2968c0b1f392c89d0dc57f Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 4 May 2017 16:22:27 +0200 Subject: Adding fast Input/Output and Manacher's algorithm. --- string/manacher.cpp | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 string/manacher.cpp (limited to 'string/manacher.cpp') diff --git a/string/manacher.cpp b/string/manacher.cpp new file mode 100644 index 0000000..8bd58fb --- /dev/null +++ b/string/manacher.cpp @@ -0,0 +1,30 @@ +char input[MAX_N]; +char s[2 * MAX_N + 1]; +int longest[2 * MAX_N + 1]; + +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'; +} + +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; +} -- cgit v1.2.3