题目描述
难度分:1700
输入长度≤4×105的字符串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=⌈n2⌉开始,n为偶数x的长度就从left=⌊n2⌋+1开始。且x必须存在相同的真后缀和真前缀,所以x的长度最多为n−1。
遍历x可能得结尾位置r∈[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;
}