#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>

template<int B, int mod>
struct Hash {
    // int B = 133331, mod = 1e9 + 7;
    vector<ll> h, p;

    Hash(string s) {
        int n = s.size();
        h.resize(n); p.assign(n, 1);
        h[0] = s[0];
        for (int i = 1; i < n; i++) {
            h[i] = h[i-1] * B + s[i];
            h[i]%=mod;
            p[i] = p[i - 1] * B % mod;
        }
    }

    ll get(int l, int r) {
        if (l > r) return 0ll;
        ll H = h[r] - h[l - 1] * p[(r - l + 1)];
        return (H % mod + mod) % mod;
    }
};
void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    auto t = s;
    reverse(t.begin(), t.end());
    s = ' ' + s + t;

    const int B = 13331, mod = 1e9 + 7;

    Hash<B, mod> hash(s);
    for (int i = 0; i <= n; i++) {
        auto h1 = hash.get(3 * n + 1 - i, 4 * n - i);
        auto h2 = (hash.get(1, i) * hash.p[(n - i)] + hash.get(n + i + 1, 2 * n)) % mod;

        if (h1 == h2) {
            cout << s.substr(1, i) + s.substr(n + i + 1, n - i) << '\n';
            cout << i << '\n';
            return;
        }
    }
    cout << "-1\n";
}

signed main() {
    // long double p = 1e18;
    // cout << powl(1 - 1 / p, 2e6) << '\n';
    int t = 1;
    while (t--) solve();
    return 0;
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/

1 条评论

  • @ 2026-7-22 11:51:17
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pii pair<int, int>
    
    template<int B, int mod>
    struct Hash {
        // int B = 133331, mod = 1e9 + 7;
        vector<ll> h, p;
    
        Hash(string s) {
            int n = s.size();
            h.resize(n); p.assign(n, 1);
            h[0] = s[0];
            for (int i = 1; i < n; i++) {
                h[i] = h[i-1] * B + s[i];
                h[i]%=mod;
                p[i] = p[i - 1] * B % mod;
            }
        }
    
        ll get(int l, int r) {
            if (l > r) return 0ll;
            ll H = h[r] - h[l - 1] * p[(r - l + 1)];
            return (H % mod + mod) % mod;
        }
    };
    void solve() {
        int n;
        cin >> n;
    
        string s;
        cin >> s;
    
        auto t = s;
        reverse(t.begin(), t.end());
        s = ' ' + s + t;
    
        const int B = 13331, mod = 1e9 + 7;
    
        Hash<B, mod> hash(s);
        for (int i = 0; i <= n; i++) {
            auto h1 = hash.get(3 * n + 1 - i, 4 * n - i);
            auto h2 = (hash.get(1, i) * hash.p[(n - i)] + hash.get(n + i + 1, 2 * n)) % mod;
    
            if (h1 == h2) {
                cout << s.substr(1, i) + s.substr(n + i + 1, n - i) << '\n';
                cout << i << '\n';
                return;
            }
        }
        cout << "-1\n";
    }
    
    signed main() {
        // long double p = 1e18;
        // cout << powl(1 - 1 / p, 2e6) << '\n';
        int t = 1;
        while (t--) solve();
        return 0;
    }
    /*
    g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
    */
    ``
    
    • 1

    信息

    ID
    499
    时间
    ms
    内存
    MiB
    难度
    6
    标签
    递交数
    58
    已通过
    17
    上传者