本文主要是介绍Codeforces Round 934 (Div. 2) ---- D. Non-Palindromic Substring --- 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
D. Non-Palindromic Substring ：
题目描述：
思路解析：
下面给出两种代码的代码实现：
代码一：线段树实现hash判断回文字符串
代码二：manacher判断回文字符串
D. Non-Palindromic Substring ：
题目描述：
假设有一个字符串长度为n， 如果这个字符串没有长度为k的回文子串，那么称这个字符串为k好字符串，现在定义f(str) = k1+k2+......，如果字符串str是一个k1字符串，k2字符串......
现在给出一个长度为n的字符串和q次查询，每次查询区间 [li,ri] 问这个区间对应的字符串的f值为多少。
思路解析：
任意一个字符串一定不是1好字符串，因为每个长度为1的子串都是回文串。
假设现在字符串长度为n，k为偶数，什么情况才能满足字符串不是k好字符串 假设k==4
那么字符串有形如 a1a2a3a4a5....的结构 假设 (a1 a2 a3 a4) 和 (a2 a3 a4 a5) 是回文的，那么可以推出a1 == a2 == a3 == a4 == a5，即只有一个字符重复的字符串才可能出现 不是 k好字符串 （k为偶数） 且此时，奇数也不为好字符串。
假设现在字符串长度为n，k为奇数，什么情况才能满足字符串不是k好字符串，假设k==3
那么字符串有形如 a1a2a3a4a5.....的结构 假设(a1a2a3) 和 (a2a3a4) 回文的，那么可以推出 a1 == a3 == a5.... a2 == a4，即只要满足是两个字符循环的字符串 （如ababab...）。可以发现此时任意长度小于等于 n的奇数k， 字符串都不是k好字符串，而且单字符循环可以看作此情况的特殊情况。
那么现在整个查询情况可以分为三类：
(1) 单字符循环的字符串， 此时f值为0
(2) 双字符循环的字符串，此时f值为 2 + 4 + ..... + m （m <= n)，如果n长度为奇数则不加n
(3) 啥也不是 此时f值 2 + 3 + 4 + ..... + n， 如果长度为n的字符串是回文字符串则减去n
则（2）f值可看作 2 + 4 + ... + m （m < n) (3) f值可看作 2 + 3 + ....+ (n-1) 这两种情况都去特判一下整个字符串是否为回文字符串即可。 这里判断字符串是否回文字符串有两种做法，hash或者manacher。
// 这里判断循环字符串可以利用边界判断的方法，详细思路请看代码，自己模拟即可
下面给出两种代码的代码实现：
代码一：线段树实现hash判断回文字符串
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int inf = (int) 2e7;static int[] ff = new int[26];static SegTree tree;public static void main(String[] args) throws IOException {pow = new long[MAXN];pow[0] = 1;for (int i = 1; i < MAXN; i++) {pow[i] = pow[i-1] * base % mod;}Random random = new Random();for (int i = 0; i < 26; i++) {ff[i] = random.nextInt(235879);}int t = f.nextInt();tree = new SegTree();while (t > 0) {solve();t--;}w.flush();w.close();br.close();}public static void solve() {n = f.nextInt();int q = f.nextInt();s = (" " + f.next()).toCharArray();TreeSet<Integer> s1 = new TreeSet<>();TreeSet<Integer> s2 = new TreeSet<>(); // 利用s1判断单字符循环， s2判断双字符循环for (int i = 1; i < n; i++) {if (s[i+1] != s[i]) s1.add(i);if (i+2 <= n && s[i] != s[i+2]) s2.add(i);}s1.add(n+1);s2.add(n+1);tree.build(1, 1, n);for (int i = 0; i < q; i++) {int l = f.nextInt();int r = f.nextInt();int len = r - l + 1;long ans = 0;if (l == r) {w.println(0); continue;}int a = s1.ceiling(l);if (a >= r) {w.println(0); continue;}else {a = s2.ceiling(l);if (a >= r - 1) ans = (long) ((len - 1) / 2) * ((len - 1) / 2 + 1);else ans = (long) len * (len - 1) / 2 - 1;}long[] b = tree.qry(1, l, r);if (b[0] != b[1]) ans += len;w.println(ans);}}static int base = 29;static int mod = (int) 1e9 + 9;static long[] pow;static int MAXN = (int) 2e5 + 5;static char[] s;static int n;public static class Node{int l,r;long[] sum = new long[2];}public static class SegTree{Node[] t = new Node[MAXN * 4];public SegTree(){for (int i = 0; i < MAXN * 4; i++) {t[i] = new Node();}}public void build(int root, int l, int r){t[root].l = l;t[root].r=r;if (t[root].l == t[root].r){t[root].sum[0] = ff[s[l] - 'a'];t[root].sum[1] = ff[s[l] - 'a'];return;}int ch = root << 1;int mid = (l + r) >> 1;build(ch, l, mid); build(ch|1, mid+1, r);update(root);}void update(int root){int ch = root << 1;int len1 = t[ch|1].r - t[ch|1].l + 1;int len2 = t[ch].r - t[ch].l + 1;t[root].sum[0] = (t[ch].sum[0] * pow[len1] % mod + t[ch|1].sum[0]) % mod;t[root].sum[1] = (t[ch].sum[1] + t[ch|1].sum[1] * pow[len2] % mod) % mod;}long[] qry(int root, int l, int r){if (t[root].l == l && t[root].r == r){return t[root].sum;}int ch = root << 1; int mid = (t[root].l + t[root].r) >> 1;if (r <= mid) return qry(ch, l, r);else if (l > mid) return qry(ch|1, l, r);else {long[] a = qry(ch, l, mid);long[] b = qry(ch|1, mid+1, r);long[] tmp = new long[2];int len1 = r - mid;int len2 = mid - l + 1;tmp[0] = (a[0] * pow[len1] % mod + b[0]) % mod;tmp[1] = (a[1] + b[1] * pow[len2] % mod) % mod;return tmp;}}}static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));static Input f = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}代码二：manacher判断回文字符串
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int inf = (int) 2e7;static int[] ff = new int[26];public static void main(String[] args) throws IOException {Random random = new Random();for (int i = 0; i < 26; i++) {ff[i] = random.nextInt(235879);}int t = f.nextInt();while (t > 0) {solve();t--;}w.flush();w.close();br.close();}public static void solve() {int n = f.nextInt();int q = f.nextInt();String str = f.next();char[] s = (" " + str).toCharArray();TreeSet<Integer> s1 = new TreeSet<>();TreeSet<Integer> s2 = new TreeSet<>();for (int i = 1; i < n; i++) {if (s[i+1] != s[i]) s1.add(i);if (i+2 <= n && s[i] != s[i+2]) s2.add(i);}s1.add(n+1);s2.add(n+1);int[] p = manacher(str.toCharArray());for (int i = 0; i < q; i++) {int l = f.nextInt();int r = f.nextInt();int len = r - l + 1;long ans = 0;if (l == r) {w.println(0); continue;}int a = s1.ceiling(l);if (a >= r) {w.println(0); continue;}else {a = s2.ceiling(l);if (a >= r - 1) ans = (long) ((len - 1) / 2) * ((len - 1) / 2 + 1);else ans = (long) len * (len - 1) / 2 - 1;}if (p[l + r - 1] < len) ans += len;w.println(ans);}}public static int[] manacher(char[] s){int n = s.length;char[] a = new char[2 * n + 1];for (int i = 0; i < n; i++) {a[2 * i] = '#';a[2 * i + 1] = s[i];}a[2 * n] = '#';return manacher_odd(a);}public static int[] manacher_odd(char[] s){int len = 0;int n = s.length;int[] p = new int[n];int r = 0;int c = 0;for (int i = 0; i < n; i++) {len = r > i ? Math.min(p[2 * c - i], r - i) : 1;while (len + i < n && i - len >= 0 && s[i + len] == s[i - len]) len++;if (len + i > r){c = i;r = len + i;}p[i] = len;}for (int i = 0; i < n; i++) {p[i]--;}return p;}static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));static Input f = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}这篇关于Codeforces Round 934 (Div. 2) ---- D. Non-Palindromic Substring --- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
