Submission #70613586

---

Source Code Expand

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)

const ll dy[] = {-1, 0, 0, 1};
const ll dx[] = {0, -1, 1, 0};

template <class T, class T1, class T2> bool isrange(T target, T1 low, T2 high) { return low <= target && target < high; }
template <class T, class U> T min(const T &t, const U &u) { return t < u ? t : u; }
template <class T, class U> T max(const T &t, const U &u) { return t < u ? u : t; }
template <class T, class U> bool chmin(T &t, const U &u) { if (t > u) { t = u; return true; } return false; }
template <class T, class U> bool chmax(T &t, const U &u) { if (t < u) { t = u; return true; } return false; }

// #include "titan_cpplib/others/print.cpp"

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;

// print

// -------------------------
// pair<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const pair<K, V>& p);
// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3> ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t);
// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4> ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t);
// vector<T>
template<typename T> ostream& operator<<(ostream& os, const vector<T>& a);
// vector<vector<T>>
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& a);
// array<T, 2>
template<typename T> ostream& operator<<(ostream& os, const array<T, 2>& a);
// set<T>
template<typename T> ostream& operator<<(ostream& os, const set<T>& s);
// multiset<T>
template<typename T> ostream& operator<<(ostream& os, const multiset<T>& s);
// unordered_set<T>
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& a);
// map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& mp);
// unordered_map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const unordered_map<K, V>& mp);
// -------------------------

// color
static const string PRINT_RED = "\033[91m"; // 赤字
static const string PRINT_GREEN = "\033[92m"; // 緑字
static const string PRINT_BLUE = "\033[94m";  // 青字
static const string PRINT_NONE = "\033[m"; // 色を元に戻す
static const string PRINT_BOLD = "\u001b[1m"; // 太字

string to_red(const string &s)   { return PRINT_RED + s + PRINT_NONE; }
string to_green(const string &s) { return PRINT_GREEN + s + PRINT_NONE; }
string to_blue(const string &s)  { return PRINT_BLUE + s + PRINT_NONE; }
string to_bold(const string &s)  { return PRINT_BOLD + s + PRINT_NONE; }

string spacefill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += " ";
    t += s;
    return t;
}

string zfill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += "0";
    t += s;
    return t;
}

string bin(long long s) {
    string t;
    while (s) {
        t += (s & 1) ? '1' : '0';
        s >>= 1;
    }
    reverse(t.begin(), t.end());
    return t;
}

void DEBUG_LINE() { cerr << "[Line] : " << __LINE__ << std::endl; }

// pair<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const pair<K, V>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
    return os;
}

// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", " << get<3>(t) << ")";
    return os;
}

// array<T, 2>
template<typename T>
ostream& operator<<(ostream& os, const array<T, 2>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<T>
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<vector<T>>
template<typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
    os << "[\n";
    int h = (int)a.size();
    for (int i = 0; i < h; ++i) {
        os << "  " << a[i] << '\n';
    }
    os << "]";
    return os;
}

// set<T>
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// multiset<T>
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_set<T>
template<typename T>
ostream& operator<<(ostream& os, const unordered_set<T>& a) {
    set<T> s(a.begin(), a.end());
    os << s;
    return os;
}

// map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& mp) {
    os << "{";
    auto it = mp.begin();
    while (it != mp.end()) {
        os << it->first << ": " << it->second;
        ++it;
        if (it != mp.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_map<K, V>& mp) {
    map<K, V> m(mp.begin(), mp.end());
    os << m;
    return os;
}

#include <vector>
#include <random>
#include <cassert>
// #include "titan_cpplib/data_structures/segment_tree.cpp"
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

namespace titan23 {

template <class T, T (*op)(T, T), T (*e)()>
class SegmentTree {
private:
    int n, _size, _log;
    vector<T> data;

    int bit_length(const int x) const {
        if (x == 0) return 0;
        return 32 - __builtin_clz(x);
    }

public:
    SegmentTree() {}

    SegmentTree(const int n) {
        _build(n);
    }

    SegmentTree(const vector<T> &a) {
        int n = (int)a.size();
        _build(n);
        for (int i = 0; i < n; ++i) {
            data[i+_size] = a[i];
        }
        for (int i = _size-1; i > 0; --i) {
            data[i] = op(data[i<<1], data[i<<1|1]);
        }
    }

    void _build(const int n) {
        this->n = n;
        this->_log = bit_length(n);
        this->_size = 1 << _log;
        this->data.resize(this->_size*2, e());
    }

    T get(int const k) const {
        return data[k+_size];
    }

    void set(int k, const T v) {
        assert(0 <= k && k < n);
        k += _size;
        data[k] = v;
        for (int i = 0; i < _log; ++i) {
            k >>= 1;
            data[k] = op(data[k<<1], data[k<<1|1]);
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        l += _size;
        r += _size;
        T lres = e(), rres = e();
        while (l < r) {
            if (l & 1) lres = op(lres, data[l++]);
            if (r & 1) rres = op(data[r^1], rres);
            l >>= 1;
            r >>= 1;
        }
        return op(lres, rres);
    }

    T all_prod() const {
        return data[1];
    }

    template<typename F>  // F: function<bool (T)> f
    int max_right(int l, F &&f) const {
        assert(0 <= l && l <= _size);
        // assert(f(e()));
        if (l == n) return n;
        l += _size;
        T s = e();
        while (1) {
            while ((l & 1) == 0) {
                l >>= 1;
            }
            if (!f(op(s, data[l]))) {
                while (l < _size) {
                    l <<= 1;
                    if (f(op(s, data[l]))) {
                        s = op(s, data[l]);
                        l |= 1;
                    }
                }
                return l - _size;
            }
            s = op(s, data[l]);
            ++l;
            if ((l & (-l)) == l) break;
        }
        return n;
    }

    template<typename F>  // F: function<bool (T)> f
    int min_left(int r, F &&f) const {
        assert(0 <= r && r <= n);
        // assert(f(e()));
        if (r == 0) return 0;
        r += _size;
        T s = e();
        while (r > 0) {
            --r;
            while (r > 1 && (r & 1)) {
                r >>= 1;
            }
            if (!f(op(data[r], s))) {
                while (r < _size) {
                    r = (r << 1) | 1;
                    if (f(op(data[r], s))) {
                        s = op(data[r], s);
                        r ^= 1;
                    }
                }
                return r + 1 - _size;
            }
            s = op(data[r], s);
            if ((r & (-r)) == r) break;
        }
        return 0;
    }

    vector<T> tovector() const {
        vector<T> res(n);
        for (int i = 0; i < n; ++i) {
            res[i] = get(i);
        }
        return res;
    }

    void print() const {
        cout << '[';
        for (int i = 0; i < n-1; ++i) {
            cout << get(i) << ", ";
        }
        if (n > 0) cout << get(n-1);
        cout << ']' << endl;
    }
};
}  // namespace titan23

using namespace std;

// HashString
namespace titan23 {

class HashStringBase {
    // ref: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
public:
    using u64 = unsigned long long;
    using u128 = __uint128_t;
    static constexpr const u64 MOD = (1ULL << 61) - 1;
    int n;
    u64 base, invpow;
    vector<u64> powb, invb;

    static u64 mul(u64 a, u64 b) {
        u128 t = (u128)a * b;
        t = (t>>61) + (t&MOD);
        if (t >= MOD) t -= MOD;
        return t;
    }

    static u64 mod(u64 a) {
        a = (a>>61) + (a&MOD);
        if (a >= MOD) a -= MOD;
        return a;
    }

    u64 pow_mod(u64 a, u64 b) {
        u64 res = 1ULL;
        while (b) {
            if (b & 1ULL) {
                res = mul(res, a);
            }
            a = mul(a, a);
            b >>= 1ULL;
        }
        return res;
    }

    HashStringBase(int n = 0) : n(n) {
        std::mt19937 rand(std::random_device{}());
        u64 base = std::uniform_int_distribution<>(414123123, 1000000000)(rand);
        // u64 base = 414123123;
        this->base = base;
        this->invpow = pow_mod(base, HashStringBase::MOD-2);
        powb.resize(n + 1, 1ULL);
        invb.resize(n + 1, 1ULL);
        for (int i = 1; i <= n; ++i) {
            powb[i] = mul(powb[i-1], base);
            invb[i] = mul(invb[i-1], this->invpow);
        }
    }

    void extend(const int cap) {
        assert(cap >= 0);
        int pre_cap = powb.size();
        powb.resize(pre_cap + cap, 0);
        invb.resize(pre_cap + cap, 0);
        for (int i = pre_cap; i < pre_cap + cap; ++i) {
            powb[i] = mul(powb[i-1], base);
            invb[i] = mul(invb[i-1], invpow);
        }
    }

    int get_cap() const {
        return powb.size();
    }

    u64 unite(u64 h1, u64 h2, int k) {
        if (k >= get_cap()) extend(k - get_cap() + 1);
        u64 t = mul(h1, powb[k]) + h2;
        if (t >= MOD) t -= MOD;
        return t;
    }
};

class HashString {
private:
    using u64 = unsigned long long;
    HashStringBase* hsb;
    int n;
    bool used_seg;
    vector<u64> data, acc;

    static u64 op(u64 s, u64 t) {
        u64 u = s + t;
        if (u > HashStringBase::MOD) u -= HashStringBase::MOD;
        return u;
    }
    static u64 e() { return 0; }
    titan23::SegmentTree<u64, op, e> seg;

public:
    HashString() {}
    HashString(HashStringBase* hsb, const string &s) : n(s.size()), used_seg(false), hsb(hsb) {
        data.resize(n);
        acc.resize(n+1, 0);
        if (n > this->hsb->get_cap()) this->hsb->extend(n - this->hsb->get_cap() + 1);
        for (int i = 0 ; i < n; ++i) {
            assert(0 <= n-i-1 && n-i-1 < hsb->powb.size());
            data[i] = this->hsb->mul(this->hsb->powb[n-i-1], s[i]-'a'+1);
            acc[i+1] = this->hsb->mod(acc[i] + data[i]);
        }
        seg = titan23::SegmentTree<u64, HashString::op, HashString::e>(data);
    }

    u64 get(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (used_seg) {
            return hsb->mul(seg.prod(l, r), hsb->invb[n - r]);
        }
        return hsb->mul(hsb->mod(4 * HashStringBase::MOD + acc[r] - acc[l]), hsb->invb[n - r]);
    }

    u64 get(int k) const {
        assert(0 <= k && k < n);
        return get(k, k+1);
    }

    void set(int k, char c) {
        assert(0 <= k && k < n);
        used_seg = true;
        seg.set(k, hsb->mul(hsb->powb[n-k-1], c-'a'+1));
    }

    vector<int> get_lcp() const {
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            int ok = 0, ng = n - i + 1;
                while (ng - ok > 1) {
                int mid = (ok + ng) / 2;
                (get(0, mid) == get(i, i + mid) ? ok : ng) = mid;
            }
            a[i] = ok;
        }
        return a;
    }
};
} // namespace titan23

titan23::HashStringBase* base;

void solve() {
    string a, b; cin >> a >> b;
    int n = a.size();
    rep(i, n) {
        a[i] = (a[i] == '0' ? 'a' : 'b');
        b[i] = (b[i] == '0' ? 'a' : 'b');
    }
    titan23::HashString A(base, a);
    titan23::HashString B(base, b);
    rep(i, n) {
        auto pref = A.get(0, i);
        auto suff = A.get(i, n);
        auto h = base->unite(suff, pref, i);
        if (h == B.get(0, n)) {
            cout << i << "\n";
            return;
        }
    }
    cout << -1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);

    base = new titan23::HashStringBase(1e6);

    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In constructor 'titan23::HashString::HashString(titan23::HashStringBase*, const std::string&)':
./Main.cpp:459:10: warning: 'titan23::HashString::used_seg' will be initialized after [-Wreorder]
  459 |     bool used_seg;
      |          ^~~~~~~~
./Main.cpp:457:21: warning:   'titan23::HashStringBase* titan23::HashString::hsb' [-Wreorder]
  457 |     HashStringBase* hsb;
      |                     ^~~
./Main.cpp:472:5: warning:   when initialized here [-Wreorder]
  472 |     HashString(HashStringBase* hsb, const string &s) : n(s.size()), used_seg(false), hsb(hsb) {
      |     ^~~~~~~~~~
In file included from /opt/atcoder/gcc/include/c++/15.2.0/cassert:46,
                 from ./Main.cpp:229:
./Main.cpp:477:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  477 |             assert(0 <= n-i-1 && n-i-1 < hsb->powb.size());
      |                                  ~~~~~~^~~~~~~~~~~~~~~~~~

Judge Result