關(guān)于#游游的回文子串#O(n)做法
游游的回文子串
https://ac.nowcoder.com/acm/contest/64272/D
)
做法：
先說(shuō) 的做法，也是在周賽中大多數(shù)人的做法：
首先我們先算單個(gè)連續(xù)01區(qū)間內(nèi)的回文個(gè)數(shù)，也就是單個(gè)區(qū)間內(nèi)的子串個(gè)數(shù)，對(duì)于長(zhǎng)度為n的字符串的非空子串個(gè)數(shù)為 %20%2F%202)
對(duì)于跨區(qū)間的回文個(gè)數(shù)，可以這么求：先固定一個(gè)連續(xù)區(qū)間，然后雙指針往左右擴(kuò)展，直到當(dāng) 
的時(shí)候，我們?nèi)?nbsp;)
為最遠(yuǎn)能擴(kuò)展的地方
注意取模！??！
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;
}
)
做法：
在 做法中，我們可以發(fā)現(xiàn)求跨區(qū)間的時(shí)候，雙指針向左右擴(kuò)展的操作，本質(zhì)上就是求以
為中心的最長(zhǎng)回文串長(zhǎng)度
這時(shí)想到了什么？！
強(qiáng)大且簡(jiǎn)單的 Manacher 算法
在得到最長(zhǎng)回文長(zhǎng)度后需要用前綴和計(jì)算區(qū)間值
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;
}
