题目描述

难度分:$1700$

输入长度$\leq 4 \times 10^5$的字符串$s$，只包含小写英文字母。

$s$是由两个字符串$x$合并得到的。如果字符串$x$存在相同的真前缀和真后缀，则可以合并。例如abca$+$abca$=$abcabca。

是否存在这样的字符串$x$？

如果不存在，输出NO。如果存在，输出YES和字符串$x$。

输入样例$1$

abrakadabrabrakadabra

输出样例$1$

YES
abrakadabra

输入样例$2$

acacacaca

输出样例$2$

YES
acacaca

输入样例$3$

abcabc

输出样例$3$

NO

输入样例$4$

abababab

输出样例$4$

YES
ababab

输入样例$5$

tatbt

输出样例$5$

NO

算法

字符串哈希

说实话这题$1700$分感觉还没有这周的前两题难，很容易想到字符串哈希的做法。当然KMP算法也是可以做的，求一遍$next$数组就行。

由于两个合并的$x$必须要有公共部分，所以如果字符串$s$的长度$n$为奇数，那么$x$的长度就从$left=\lceil \frac{n}{2} \rceil$开始，$n$为偶数$x$的长度就从$left=\lfloor \frac{n}{2} \rfloor + 1$开始。且$x$必须存在相同的真后缀和真前缀，所以$x$的长度最多为$n-1$。

遍历$x$可能得结尾位置$r \in [left-1,n-1)$，只要前缀$[0,r]$的哈希值与后缀$[n-r-1,n-1]$的哈希值相等，就找到了这个$x$，即为前缀$[0,r]$。

注意为了避免$CF$上对字符串哈希算法的攻击，可以采用双哈希来降低字符串哈希的碰撞概率。

复杂度分析

时间复杂度

字符串哈希的预处理时间复杂度为$O(n)$，遍历$r$的时间复杂度也为$O(n)$，所以算法的时间复杂度为$O(n)$。

空间复杂度

空间消耗就在于字符串哈希的消耗，是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;

class StringHash {
public:
    explicit StringHash(string& s, int base1=131, int base2=13131) {
        n = s.size();
        p1.resize(n + 1);
        h1.resize(n + 1);
        p2.resize(n + 1);
        h2.resize(n + 1);
        p1[0] = p2[0] = 1;
        for(int i = 1; i <= n; i++){
            h1[i] = (h1[i - 1] * base1 % MOD + s[i - 1]) % MOD;
            p1[i] = p1[i - 1] * base1 % MOD;
            h2[i] = (h2[i - 1] * base2 % MOD + s[i - 1]) % MOD;
            p2[i] = p2[i - 1] * base2 % MOD;
        }
    }

    pair<LL, LL> shash(int left, int right, bool is_rev=false) {
        ++left, ++right;
        LL u1 = (h1[right] - h1[left - 1]*p1[right - left + 1]%MOD + MOD) % MOD;
        LL u2 = (h2[right] - h2[left - 1]*p2[right - left + 1]%MOD + MOD) % MOD;
        return {u1, u2};
    }

private:
    int base1, base2, n;
    vector<LL> h1, p1, h2, p2;
};

int main() {
    string s;
    cin >> s;
    int n = s.size();
    StringHash sh(s);
    for(int r = (n&1? (n + 1)/2: n/2 + 1) - 1; r < n - 1; r++) {
        int len = r + 1;
        auto L = sh.shash(0, r);
        auto R = sh.shash(n - len, n - 1);
        int overlap = len*2 - n;
        if(L.first == R.first && L.second == R.second) {
            cout << "YES\n";
            cout << s.substr(0, len) << endl;
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}