关于#游游的回文子串#O(n)做法
游游的回文子串
https://ac.nowcoder.com/acm/contest/64272/D
)
做法：
先说 的做法，也是在周赛中大多数人的做法：
首先我们先算单个连续01区间内的回文个数，也就是单个区间内的子串个数，对于长度为n的字符串的非空子串个数为 %20%2F%202)
对于跨区间的回文个数，可以这么求：先固定一个连续区间，然后双指针往左右扩展，直到当 
的时候，我们取 )
为最远能扩展的地方
注意取模！！！
c++ 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
void solve() {
int n; cin >> n;
int ans = 0;
for(int i = 0; i < n; i ++){
cin >> a[i];
ans = (ans + (a[i] * (a[i] + 1)) % mod * 500000004) % mod;
}
for(int i = 1; i < n - 1; i ++){
int l = i - 1, r = i + 1;
int ls = a[l], rs = a[r];
while(a[l] == a[r] && (l - 1) >= 0 && (r + 1) < n){
l --;
r ++;
ls += a[l];
rs += a[r];
}
ans += min(ls, rs);
ans %= mod;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
int t = 1; //cin >> t;
while(t --) solve();
return 0;
}
)
做法：
在 做法中，我们可以发现求跨区间的时候，双指针向左右扩展的操作，本质上就是求以
为中心的最长回文串长度
这时想到了什么？！
强大且简单的 Manacher 算法
在得到最长回文长度后需要用前缀和计算区间值
c++ 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int a[N], sum[N], d1[N];
void solve() {
int n; cin >> n;
int ans = 0;
for(int i = 1; i <= n; i ++){
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
ans = (ans + (a[i] * (a[i] + 1)) % mod * 500000004) % mod;
}
//Manacher
for (int i = 1, l = 1, r = 0; i <= n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && a[i - k] == a[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
for(int i = 2; i < n; i ++){
int l = i - d1[i], r = i + d1[i];
ans += (sum[r - 1] - sum[l] - a[i]) % mod * 500000004 % mod + min(a[l], a[r]);
ans %= mod;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
int t = 1; //cin >> t;
while(t --) solve();
return 0;
}
查看18道真题和解析
