ABC 430 E - Shift String

题目大意

给两个长度相同的 01 串 A 和 B。一次操作可以把 A 的第一个字符搬到末尾，也就是做一次左循环位移。

要对每个测试用例求最少操作次数，使得 A = B。如果不管怎么循环位移都不可能相等，就输出 -1。

输入格式

第一行是测试组数 T。每组测试给两行：

A
B

数据范围

• 测试组数：1 <= T <= 10000

• A 和 B 都是只包含 0 / 1 的字符串。

• 每组字符串长度满足：2 <= len(A) = len(B) <= 10^6

• 单个输入中，所有测试用例的 len(A) 之和不超过 10^6

样例

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

输出：

2
-1
0
-1
22

第一组里，1010001 -> 0100011 -> 1000110，做 2 次就能变成 B。

思路讲解

一句话

这题本质上是在问：B 是不是 A 的某个循环位移；如果是，就找最小的左移次数。直接拼 A + A 然后找 B 也能做，这里用 0-based 字符串哈希模板，把每次“弹出头字符 + 追加到尾部”的变化维护成 O(1)。

把循环位移看成哈希上的 pop / push

字符串哈希和十进制数很像：越靠前的字符权重越高。设当前串长度为 n，哈希值是

$$h = s_0 \cdot base^{n-1} + s_1 \cdot base^{n-2} + \cdots + s_{n-1}.$$

做一次左循环位移，相当于两步：

操作	对哈希的影响
把首字符 ch 从最高位删掉	h -= ch * base^(n - 1)
把 ch 放到末尾	h = h * base + ch

所以每次转一下，不需要真的改字符串，也不需要重新算整段哈希。

关键不变量：h1.hashval 始终等于当前这一次循环位移后的 A 的完整哈希值。

模板本身提供的是末尾 push/pop 和 0-based get(l,r)；这道题的操作是“删头 + 加尾”，所以在完整串哈希上单独写两个小函数：

auto popFront = [&](char ch) {
    h1.hashval -= U(ch) * h1.powBase[n - 1];
};

auto pushBack = [&](char ch) {
    h1.hashval *= base;
    h1.hashval += U(ch);
};

为什么只需要枚举 n - 1 次

如果一开始 A = B，答案就是 0。

否则每做一次操作就是左移一位。长度为 n 的字符串转 n 次会回到原串，所以只需要检查 1 到 n - 1 次。第一次遇到哈希相等的位置，就是最小操作次数。

if (h1.hashval == h2.hashval) {
    cout << 0 << "\n";
    return;
}

FOR(i, 0, SZ(s1) - 2) {
    popFront(s1[i]);
    pushBack(s1[i]);
    if (h1.hashval == h2.hashval) {
        cout << i + 1 << "\n";
        return;
    }
}
cout << -1 << "\n";

模数选择

这里用的是 2^61 - 1 这个 Mersenne prime 风格的哈希模数。乘法时用 __uint128_t 接住，再用折叠方式取模，碰撞概率很低，速度也比较舒服。

这版模板还有两个实用细节：

功能	用处
get(l, r)	内部 0-based，返回 s[l..r] 的哈希，还会自动修正边界
push(c) / pop()	维护“末尾追加 / 末尾删除”的在线哈希，适合栈式字符串处理

普通 unsigned long long 自然溢出也能写，但这题总长度到 10^6，用 2^61 - 1 会更安心一点。

复杂度

每个测试用例只初始化一次哈希和幂数组，然后枚举所有循环位移。

时间复杂度是 O(n)，空间复杂度是 O(n)。所有测试的总长度不超过 10^6，所以稳过。

AC 代码

AC 提交链接

源码较长，下面折叠完整 C++。

展开完整源码

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll) 1e9 + 7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

struct U {
    using u128 = __uint128_t;
    static constexpr ll MOD = (1ULL << 61) - 1;

    ll v;

    U() : v(0) {
    }

    U(ll x) {
        ll t = x % MOD;
        if (t < 0) t += MOD;
        v = (ll) t;
    }

    static inline ll add(ll a, ll b) {
        ll s = a + b;
        if (s >= MOD) s -= MOD;
        return s;
    }

    static inline ll sub(ll a, ll b) {
        return (a >= b) ? (a - b) : (a + MOD - b);
    }

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

    U &operator+=(const U &o) {
        v = add(v, o.v);
        return *this;
    }

    U &operator-=(const U &o) {
        v = sub(v, o.v);
        return *this;
    }

    U &operator*=(const U &o) {
        v = mul(v, o.v);
        return *this;
    }

    friend U operator+(U a, const U &b) {
        a += b;
        return a;
    }

    friend U operator-(U a, const U &b) {
        a -= b;
        return a;
    }

    friend U operator*(U a, const U &b) {
        a *= b;
        return a;
    }

    friend bool operator==(const U &a, const U &b) { return a.v == b.v; }
    friend bool operator!=(const U &a, const U &b) { return a.v != b.v; }
    friend bool operator<(const U &a, const U &b) { return a.v < b.v; }
    friend bool operator>(const U &a, const U &b) { return a.v > b.v; }
    friend bool operator<=(const U &a, const U &b) { return a.v <= b.v; }
    friend bool operator>=(const U &a, const U &b) { return a.v >= b.v; }
};

const U base = 131;

// AC https://vjudge.net/solution/65151535 string matching 测试了find函数功能
// 2025/11/4
// AC https://www.luogu.com.cn/record/245201000 测试了这个push，pop，以及增强get鲁棒性。
// 2026/3/21 改为了 0-based
struct HS {
    vector<U> hs, powBase;
    U hashval;
    ll n;
    string s;

    HS(const string &ls) {
        n = SZ(ls);
        s = ls;
        hs.assign(n, 0);
        powBase.assign(n + 1, 0);
        powBase[0] = 1;
        for (ll i = 1; i <= n; ++i) {
            powBase[i] = powBase[i - 1] * base;
        }
        if (n > 0) {
            hs[0] = U(s[0]);
            for (ll i = 1; i < n; ++i) {
                hs[i] = hs[i - 1] * base + U(s[i]);
            }
            hashval = hs[n - 1];
        } else {
            hashval = 0;
        }
    }

    U get(ll l, ll r) {
        if (n == 0) return 0;
        l = max(0ll, l);
        r = min(n - 1, r);
        if (l > r) return 0;
        if (l == 0) return hs[r];
        return hs[r] - hs[l - 1] * powBase[r - l + 1];
    }

    U get(ll l) {
        return get(l, n - 1);
    }

    ll find(const string &ls) {
        U hxfind = 0;
        ll m = SZ(ls);
        if (m == 0) return n + 1;
        if (m > n) return 0;
        for (ll i = 0; i < m; ++i) {
            hxfind = hxfind * base + ls[i];
        }
        ll res = 0;
        for (ll r = m - 1; r < n; ++r) {
            U hx = get(r - m + 1, r);
            if (hx == hxfind) {
                res++;
            }
        }
        return res;
    }

    void pop() {
        if (n == 0) return;
        n--;
        s.pop_back();
        if (n == 0) {
            hs.clear();
            hashval = 0;
            return;
        }
        hs.pop_back();
        hashval = hs.back();
    }

    void push(char c) {
        s.push_back(c);
        if (n == 0) {
            hs.push_back(U(c));
        } else {
            hs.push_back(hs.back() * base + U(c));
        }
        n++;
        hashval = hs.back();
        if (SZ(powBase) <= n) {
            powBase.push_back(powBase.back() * base);
        }
    }
};

void Solve() {
    string s1, s2;
    cin >> s1 >> s2;
    HS h1(s1), h2(s2);
    ll n = SZ(s1);

    if (h1.hashval == h2.hashval) {
        cout << 0 << "\n";
        return;
    }

    auto popFront = [&](char ch) {
        h1.hashval -= U(ch) * h1.powBase[n - 1];
    };
    auto pushBack = [&](char ch) {
        h1.hashval *= base;
        h1.hashval += U(ch);
    };

    FOR(i, 0, n - 2) {
        popFront(s1[i]);
        pushBack(s1[i]);
        if (h1.hashval == h2.hashval) {
            cout << i + 1 << "\n";
            return;
        }
    }
    cout << -1 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> lT;
    while (lT--) Solve();
    return 0;
}

心路历程（WA，TLE，MLE……）

本地 Obsidian 笔记里没有记录这题的 WA / TLE。比较容易踩的点主要有两个：

• 哈希递推方向要统一：前面的字符是高位，所以删首字符时删的是 ch * base^(n - 1)。

• 循环次数不要多枚举：如果检查完 n - 1 次还没有相等，下一次就回到原串了，答案只能是 -1。

附件

暂无附件。