例题一：插入反转字符串

定义函数 f(i) 为在字符串 S 的第 i 个元素后面插入反转后的字符串 S.

例如若字符串 S = abc，则 f(2) = abcbac.

现题目给出了函数 f(i) 的值，请你求出满足条件的 S 和 i，答案可能不唯一，输出其中一个即可；若找不到满足条件的，就输出 -1.

输入格式

第一行输入一个整数 n 代表字符串 S 的长度.

第二行输入一个长度为 2 * n 的字符串，代表 f(i) 的值.

输出格式

若能找到满足条件的 S 和 i，则第一行输出 S，第二行输出 i;

若找不到满足条件的，只需要输出 -1 即可。

样例一

输入：

4
abababab

输出：

abab
1

样例二

输入：

4
atcodeer

输出：

-1

字符串哈希

自然溢出, 冲突样例 5 个！

#include <iostream>
#include <fstream>
#include <string>

using namespace std;
typedef long long LL;
const LL N = (LL)(3e6 + 10);

typedef unsigned long long ULL;
ULL B = 233, R[N], H1[N], H2[N];
int n;
string s;

void init()
{
    R[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        R[i] = R[i - 1] * B;
    }

    for (int i = 1; i <= n; i ++)
    {
        H1[i] = H1[i - 1] * B + s[i - 1];
        H2[i] = H2[i - 1] * B + s[n - i];
    }
}

ULL get_hash(ULL H[], int l, int r)
{
    return H[r] - H[l - 1] * R[r - l + 1];
}

ULL mul_rk(ULL x, int k)
{
    return x * R[k];
}

void solve(void)
{
    cin >> n >> s;
    int m = n; n *= 2;
    init(); 
    for (int i = 1; i <= m; i ++)
    {
        ULL t1 = mul_rk(get_hash(H1, 1, i), m - i) + get_hash(H1, m + i + 1, n);
        ULL t2 = get_hash(H2, m - i + 1, n - i);
        if (t1 == t2)
        {
            for (int j = i + m - 1; j >= i; j --) cout << s[j];
            cout << endl << i << endl; return;
        }
    }
    cout << -1 << endl;
}

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo.close(); fi.close();
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}

用质数 1e9+7 取模

#include <iostream>
#include <fstream>

using namespace std;
typedef long long LL;
const LL N = (LL)(3e6 + 10);

const LL M = LL(1e9 + 7);
const LL B = 131;
LL R[N] = {1}, h1[N], h2[N];

LL n; 
string s;

void solve(void)
{
    cin >> n >> s;

    for (LL i = 1; i <= 2 * n; i ++)
    {
        R[i] = (R[i - 1] * B) % M;
    }

    for (LL i = 1; i <= 2 * n; i ++)
    {
        h1[i] = (h1[i - 1] * B + s[i - 1]) % M;
        h2[i] = (h2[i - 1] * B + s[2 * n - i]) % M;
    }

    for (LL i = 1; i <= n; i ++)
    {
        LL t1 = ((h1[i] * R[n - i]) % M + (h1[2 * n] - (h1[n + i] * R[n - i]) % M + M)) % M;
        LL t2 = (h2[2 * n - i] - (h2[n - i] * R[n]) % M + M) % M;
        if (t1 == t2)
        {
            for (LL j = i + n - 1; j >= i; j --)
                cout << s[j];
            cout << endl << i << endl; return;
        }
    }
    cout << -1 << endl;
}

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo.close(); fi.close();
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}