C o d e f o r c e s R o u n d 934 ( D i v . 2 ) \Huge{Codeforces Round 934 (Div. 2)} CodeforcesRound934(Div.2)
D . N o n − P a l i n d r o m i c S u b s t r i n g \large{D. Non-Palindromic Substring} D.Non−PalindromicSubstring
文章目录
- 题意
- 思路
- 标程
题意
给出一个字符串 s s s,然后给出若干次查询,每次查询是对 s s s的子段 s [ l , r ] s[l,r] s[l,r]进行判断,具体为:**对于子段$ s[l,r] 中长度为 中长度为 中长度为k 的子串,如果存在不是回文的子串,则将该长度 的子串,如果存在不是回文的子串,则将该长度 的子串,如果存在不是回文的子串,则将该长度k 加上 ∗ ∗ 。对于每次查询,输出子段 加上**。对于每次查询,输出子段 加上∗∗。对于每次查询,输出子段s[l,r]$的长度之和。
思路
这是一道考察 M a n a c h a r Manachar Manachar算法的好题。
让我们先来观察题目性质:
对于任意字符串 s s s,若其本身不是回文字符串,则其子串中必然包含长度从 2... s . s i z e ( ) 2...s.size() 2...s.size()的非回文子串。
证明如下:
若字符串s中存在任意一个长度为 k ( 2 ≤ k ≤ s . s i z e ( ) ) k(2\le k \le s.size()) k(2≤k≤s.size())的子字符串全都是回文字符串,则我们可以根据 k k k构造出 s s s,且 s s s为回文字符串。
根据上述证明,我们可以发现一个性质:
1. 当偶数长度的子串是回文时:
- 如果其偶数子串全都是回文串,则如果第i位填了字符 c h ch ch,那么第 i + 1 i+1 i+1位也一定是 c h ch ch,因为长度为 2 2 2的字符串也要求回文。所以,当且仅当整个串全部相同时,才会全都是回文。
2. 当奇数长度的子串是回文时:
-
对于奇数长度,整个串全部相同是一种情况。
-
另一种情况是 a b a b a ababa ababa,即规定前两个字符,然后推导出后面的字符。这样奇数长度的子串全部为回文串。
需要注意的是,当其本身就是回文字符串时,不能加上本身长度。
然后跟据 M a n a c h a r Manachar Manachar算法,我们可以预处理字符串,然后每次可以 O ( 1 ) O(1) O(1)查询出当前子串是否为回文子串。
标程
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long
#define ULL unsigned long long
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
const int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 1e6 + 10;
string add(string s) {
string str;
int len_s = s.size();
if(len_s == 0) return "^@";
str += '^';
for (int i = 0; i < len_s; i++) {
str += '#'; str += s[i];
}
str+="#@";
return str;
}
string manacher_P(string s, vector<int> &P) {
string str;
str = add(s);
int maxid = 0, mid = 0;
//int l, r, sum; //Manacher求所有回文子串
int len_str = str.size();
P.resize(len_str);
for (int i = 1; i < len_str - 1; i++) {
if(maxid > i) P[i] = min(P[2 * mid - i], maxid - i);//进行三种情况的判断
else P[i] = 1;// 等于 R 的情况
while (str[i + P[i]] == str[i - P[i]]) P[i]++; //中心拓展
if (i + P[i] > maxid) {//如果当前回文串已经覆盖到了原先没有覆盖到的地方,则更新标记
maxid = i + P[i]; mid = i;
}
//Manacher求所有回文子串
//l = (i - 1) / 2 - (P[i] - 1) / 2;
//r = (i - 1) / 2 + (P[i] - 1) / 2;
//if(P[i] & 1) r --;
//sum += (r - l + 2) / 2;
}
//return sum; //Manacher求所有回文子串个数
int maxlen = 0, t = 0;
for(int i = 1; i < len_str - 1; i ++ ) {
if(P[i] > maxlen) {
maxlen = P[i]; t = i;
}
}
int st = (t - maxlen) >> 2;
return s.substr(st, st + maxlen - 1); //返回s中最长公共子串
}
void Solved() {
int n, q; cin >> n >> q;
string s; cin >> s;
vector<int> p, f1(n), f2(n);
auto t = manacher_P(s, p);
for(int i = n - 1; i >= 0; i -- ) {
if(i + 1 < n && s[i + 1] == s[i]) f1[i] = f1[i + 1];
else f1[i] = i + 1;
if(i + 2 < n && s[i + 2] == s[i]) f2[i] = f2[i + 2];
else f2[i] = i + 2;
}
while(q -- ) {
int l, r; cin >> l >> r; l --;
int len = r - l;
int res = 0;
if(f1[l] < r) {//不是全部相当
int temp = (len - 1) - (len - 1) % 2;
if(temp >= 2) res += (temp + 2) * ((temp - 2) / 2 + 1) / 2;
}
if(f2[l] < r || f2[l + 1] < r) {//非ababa型
int temp = (len - 1) - len % 2;
if(temp >= 3) res += (temp + 3) * ((temp - 3) / 2 + 1) / 2;
}
if(p[l + r + 1] < len) res += len;//当不是回文串时
cout << res << endl;
}
}
signed main(void) {
IOS
int ALL = 1;
cin >> ALL;
while(ALL -- ) Solved();
// cout << fixed;//强制以小数形式显示
// cout << setprecision(n); //保留n位小数
return 0;
}