Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/string/manacher.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/string/manacher.hpp"
vector<int> brute(const string& s) {
    const int n = (int)s.size();
    if(n == 0) return {};
    vector<int> res(2 * n - 1);
    for(int c = 0; c < 2 * n - 1; ++c) {
        for(int len = (c % 2 == 0);; len += 2) {
            const int l = (c - len + 1) / 2;
            const int r = (c + len + 1) / 2;
            if(l < 0 or n < r) break;
            bool ok = true;
            for(int i = l, j = r - 1; i < j; ++i, --j) {
                if(s[i] != s[j]) {
                    ok = false;
                    break;
                }
            }
            if(ok) res[c] = len;
        }
    }
    return res;
}
int main() {
    assert(manacher(string()).empty());
    assert(manacher(string("ab")) == vector<int>({1, 0, 1}));
    assert(manacher(string("aa")) == vector<int>({1, 2, 1}));
    assert(manacher(string("abba")) == vector<int>({1, 0, 1, 4, 1, 0, 1}));
    for(int n = 0; n <= 9; ++n) {
        for(int bit = 0; bit < (1 << n); ++bit) {
            string s(n, 'a');
            for(int i = 0; i < n; ++i) {
                if((bit >> i) & 1) s[i] = 'b';
            }
            assert(manacher(s) == brute(s));
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/string/manacher.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/string/manacher.hpp"
template <typename T>
vector<int> manacher(const T& s) {
    const int n = (int)s.size();
    if(n == 0) return {};
    vector<int> odd(n), even(n), res(2 * n - 1);
    for(int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = (i > r ? 1 : min(odd[l + r - i], r - i + 1));
        while(0 <= i - k and i + k < n and s[i - k] == s[i + k]) ++k;
        odd[i] = k;
        if(i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }
    for(int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = (i > r ? 0 : min(even[l + r - i + 1], r - i + 1));
        while(0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]) ++k;
        even[i] = k;
        if(i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }
    for(int i = 0; i < n; ++i) {
        res[2 * i] = 2 * odd[i] - 1;
        if(i) res[2 * i - 1] = 2 * even[i];
    }
    return res;
}
#line 4 "verify/unit_test/string/manacher.test.cpp"
vector<int> brute(const string& s) {
    const int n = (int)s.size();
    if(n == 0) return {};
    vector<int> res(2 * n - 1);
    for(int c = 0; c < 2 * n - 1; ++c) {
        for(int len = (c % 2 == 0);; len += 2) {
            const int l = (c - len + 1) / 2;
            const int r = (c + len + 1) / 2;
            if(l < 0 or n < r) break;
            bool ok = true;
            for(int i = l, j = r - 1; i < j; ++i, --j) {
                if(s[i] != s[j]) {
                    ok = false;
                    break;
                }
            }
            if(ok) res[c] = len;
        }
    }
    return res;
}
int main() {
    assert(manacher(string()).empty());
    assert(manacher(string("ab")) == vector<int>({1, 0, 1}));
    assert(manacher(string("aa")) == vector<int>({1, 2, 1}));
    assert(manacher(string("abba")) == vector<int>({1, 0, 1, 4, 1, 0, 1}));
    for(int n = 0; n <= 9; ++n) {
        for(int bit = 0; bit < (1 << n); ++bit) {
            string s(n, 'a');
            for(int i = 0; i < n; ++i) {
                if((bit >> i) & 1) s[i] = 'b';
            }
            assert(manacher(s) == brute(s));
        }
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page