Problem link, link: https://codeforces.net/contest/1679/problem/E

Part 1: Notations

$$$s$$$: The original string that might contain '?'.

$$$s[i,j]$$$: The substring including $$$s[i]$$$ and $$$s[j]$$$: $$$(s[i], s[i+1],..., s[j])$$$. If $$$i > j$$$, the $$$s[i, j]$$$ is an empty string.

$$$t$$$: The query string.

We also define some notations that will be clarified in the Part 2:

$$$ok[i,j]$$$: A $$$2D$$$ bool array indicating whether $$$s[i,j]$$$ is valid or not. We will define the word "valid" in Part 2. If $$$s[i,j]$$$ is valid, then $$$ok[i,j]$$$ is true, i.e., $$$1$$$. If $$$s[i,j]$$$ is invalid, then $$$ok[i,j]$$$ is false, i.e., $$$0$$$.

$$$set[i, j]$$$: The required character set to make $$$s[i,j]$$$ a palindrome.

$$$free[i, j]$$$: The number of free places. We will define the terminology "free places" in part 2.

$$$num[i, j]$$$: The number of '?' in the substring $$$s[i, j]$$$. For example, if s[i, j] == "???a", then $$$num[i, j] == 3$$$.

Part 2: ok, set and free

(1)We call a substring $$$s[i,j]$$$ invalid if and only if:

there exists an index $$$x (i \leq x \leq j)$$$ such that s[x] != '?' && s[i+j-x] != '?' && s[x] != s[i+j-x].

For example,

"ab?a" is valid.

"ax?xc" is invalid because the first character 'a' mismatches with the last character 'c'.

"tbct" is invalid because 'b' != 'c'

The validity of a substring is irrelevant to the query subset. For example, if the query set $$$t$$$ does not contain the character 'b', we still call the string "ab?a" valid, although it certainly cannot form a palindrome. We will deal this case using the $$$set$$$ array.

(2) $$$set[i, j]$$$ denotes all the characters needed to make $$$s[i, j]$$$ a palindrome. For example, if s[i, j] == "ab?a", then set[i, j] == {b}, as we need a character 'b' to fill in the '?'. Note that there are at most $$$17$$$ query characters in this problem, i.e., $$$|t| \leq 17$$$, so we can compress $$$set[i, j]$$$ to a $$$32$$$-bit integer to accelerate computation. Don't use std::set!

(3) $$$free[i, j]$$$ means the number of free characters in the substring $$$s[i, j]$$$. For example, in "ax?xc", the middle '?' is a free character as we could replace it with any character in the query string $$$t$$$. In "ab???a", the first and the second '?' count one free character (Warning: not two!!!). The first '?' can be replaced with an arbitrary character from $$$t$$$, and the second '?' has to be the same with the first '?', so only one of them is free. The third '?' is not free because it has to be 'b'.

Part 3: The naive formula

What is the naive formula for each query string $$$t$$$? It is:

$$$ans(t) = \sum\limits_{1 \leq i,j \leq len(s)} ok[i, j] \cdot [set[i, j] \subseteq t] \cdot |t|^{free[i, j] + num[1, i-1] + num[j+1, len(s)]}$$$ (1)

The $$$[set[i, j] \subseteq t]$$$ is like a Kronecker symbol. If $$$set[i, j] \subseteq t$$$ is true, then $$$[set[i, j] \subseteq t]==1$$$, otherwise $$$[set[i, j] \subseteq t]==0$$$. We need to analyze each $$$i, j$$$. If $$$ok[i, j]$$$ is $$$0$$$, it would never be a palindrome no matter how you fill in the '?'. If $$$ok[i, j]$$$ is $$$1$$$, it depends on the query string $$$t$$$. In part 2, I say that "ab?a" is valid even if $$$t$$$ does not contain 'b'. In this case, $$$ok[i, j]==1$$$ but $$$[set[i, j] \subset t] == 0$$$, the contribution of $$$i,j$$$ is still $$$0$$$. Be careful with the third item, how many strings $$$s$$$ can make $$$s[i, j]$$$ a palindrome? If you only count $$$|t|^{free[i, j]}$$$, you are wrong! Because we can use arbitrary characters to fill in the '?' in $$$s[1, i-1]$$$ and $$$s[j+1, len(s)]$$$, that doesn't affect whether $$$s[i, j]$$$ is a palindrome or not! So, we should not forget $$$num[1, i-1]$$$ and $$$num[j+1, len(s)]$$$.

Part 4: Computation

What is the bottleneck of the naive formula Eq.(1)? Obviously, it takes $$$O(n^2)$$$ for every query, which is too slow. We first figure out:

(1) Computing $$$ok,\,set,\,free$$$ requires $$$O(n^2)$$$ time. Possibly there are $$$O(n)$$$ algorithms, but I don't know. Anyway, $$$O(n^2)$$$ is sufficient to pass. The idea is simple. For odd-length palindromes, we extend from one central character. For even-length palindromes, we extend from two adjacent characters. Initialize the $$$ok$$$ array to $$$0$$$, when you extend, set $$$ok[i, j]$$$ to $$$1$$$, and stop extension when you encounter an invalid pair $$$(i, j)$$$, i.e., s[i] != '?' && s[j] != '?' && s[i] != s[j]!