Manacher's algorithm testcases (#1393)

yuuurchyk · Yurii A. · adamant-pwn · web-flow · commit 429529980717 · 2025-03-24T20:49:18.000+01:00
* Fix inconsistencies in Manacher's algorithm

* Add test for manacher_odd

* Update test_manacher_odd.cpp

* empty commit to run tests?

---------

Co-authored-by: Yurii A. &lt;l.soho@tuta.io&gt;
Co-authored-by: Oleksandr Kulkov &lt;adamant.pwn@gmail.com&gt;
diff --git a/src/string/manacher.md b/src/string/manacher.md
@@ -49,7 +49,7 @@ Such an algorithm is slow, it can calculate the answer only in $O(n^2)$.
 The implementation of the trivial algorithm is:
 
 ```cpp
-vector<int> manacher_odd(string s) {
+vector<int> manacher_odd_trivial(string s) {
     int n = s.size();
     s = "$" + s + "^";
     vector<int> p(n + 2);
@@ -68,7 +68,7 @@ Terminal characters `$` and `^` were used to avoid dealing with ends of the stri
 
 We describe the algorithm to find all the sub-palindromes with odd length, i. e. to calculate $d_{odd}[]$.
 
-For fast calculation we'll maintain the **borders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
+For fast calculation we'll maintain the **exclusive borders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
 
 So, we want to calculate $d_{odd}[i]$ for the next $i$, and all the previous values in $d_{odd}[]$ have been already calculated. We do the following:
 
@@ -140,12 +140,12 @@ For calculating $d_{odd}[]$, we get the following code. Things to note:
  - The while loop denotes the trivial algorithm. We launch it irrespective of the value of $k$.
  - If the size of palindrome centered at $i$ is $x$, then $d_{odd}[i]$ stores $\frac{x+1}{2}$.
 
-```cpp
+```{.cpp file=manacher_odd}
 vector<int> manacher_odd(string s) {
     int n = s.size();
     s = "$" + s + "^";
     vector<int> p(n + 2);
-    int l = 1, r = 1;
+    int l = 0, r = 1;
     for(int i = 1; i <= n; i++) {
         p[i] = max(0, min(r - i, p[l + (r - i)]));
         while(s[i - p[i]] == s[i + p[i]]) {
diff --git a/test/test_manacher_odd.cpp b/test/test_manacher_odd.cpp
@@ -0,0 +1,74 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+#include "manacher_odd.h"
+
+string getRandomString(size_t n, uint32_t seed, char minLetter='a', char maxLetter='b') {
+    assert(minLetter <= maxLetter);
+    const size_t nLetters = static_cast<int>(maxLetter) - static_cast<int>(minLetter) + 1;
+    std::uniform_int_distribution<size_t> distr(0, nLetters - 1);
+    std::mt19937 gen(seed);
+
+    string res;
+    res.reserve(n);
+
+    for (size_t i = 0; i < n; ++i)
+        res.push_back('a' + distr(gen));
+
+    return res;
+}
+
+bool testManacherOdd(const std::string &s) {
+    const auto n = s.size();
+    const auto d_odd = manacher_odd(s);
+
+    if (d_odd.size() != n)
+        return false;
+
+    const auto inRange = [&](size_t idx) {
+        return idx >= 0 && idx < n;
+    };
+
+    for (size_t i = 0; i < n; ++i) {
+        if (d_odd[i] < 0)
+            return false;
+        for (int d = 0; d < d_odd[i]; ++d) {
+            const auto idx1 = i - d;
+            const auto idx2 = i + d;
+
+            if (!inRange(idx1) || !inRange(idx2))
+                return false;
+            if (s[idx1] != s[idx2])
+                return false;
+        }
+
+        const auto idx1 = i - d_odd[i];
+        const auto idx2 = i + d_odd[i];
+        if (inRange(idx1) && inRange(idx2) && s[idx1] == s[idx2])
+            return false;
+    }
+
+    return true;
+}
+
+int main() {
+    vector<string> testCases;
+
+    testCases.push_back("");
+    for (size_t i = 1; i <= 25; ++i) {
+        auto s = string{};
+        s.resize(i, 'a');
+        testCases.push_back(move(s));
+    }
+    testCases.push_back("abba");
+    testCases.push_back("abccbaasd");
+    for (size_t n = 9; n <= 100; n += 10)
+        testCases.push_back(getRandomString(n, /* seed */ n, 'a', 'd'));
+    for (size_t n = 7; n <= 100; n += 10)
+        testCases.push_back(getRandomString(n, /* seed */ n));
+
+    for (const auto &s: testCases)
+        assert(testManacherOdd(s));
+
+    return 0;
+}
