Non-Palindromic Substring (Codeforces 1943B)
Tags: Math, hashing

A string $$$t$$$ is said to be $$$k$$$-good if there exists at least one substring$$$^\dagger$$$ of length $$$k$$$ which is not a palindrome$$$^\ddagger$$$. Let $$$f(t)$$$ denote the sum of all values of $$$k$$$ such that the string $$$t$$$ is $$$k$$$-good.You are given a string $$$s$$$ of length $$$n$$$. You will have to answer $$$q$$$ of the following queries:  Given $$$l$$$ and $$$r$$$ ($$$l < r$$$), find the value of $$$f(s_ls_{l + 1}\ldots s_r)$$$. $$$^\dagger$$$ A substring of a string $$$z$$$ is a contiguous segment of characters from $$$z$$$. For example, "$$$\mathtt{defor}$$$", "$$$\mathtt{code}$$$" and "$$$\mathtt{o}$$$" are all substrings of "$$$\mathtt{codeforces}$$$" while "$$$\mathtt{codes}$$$" and "$$$\mathtt{aaa}$$$" are not.$$$^\ddagger$$$ A palindrome is a string that reads the same backwards as forwards. For example, the strings "$$$\texttt{z}$$$", "$$$\texttt{aa}$$$" and "$$$\texttt{tacocat}$$$" are palindromes while "$$$\texttt{codeforces}$$$" and "$$$\texttt{ab}$$$" are not.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$), the size of the string and the number of queries respectively.The second line of each test case contains the string $$$s$$$. It is guaranteed the string $$$s$$$ only contains lowercase English characters.The next $$$q$$$ lines each contain two integers, $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$). It is guaranteed the sum of $$$n$$$ and the sum of $$$q$$$ both do not exceed $$$2 \cdot 10^5$$$.

Output: For each query, output $$$f(s_ls_{l + 1}\ldots s_r)$$$.

Note: In the first query of the first test case, the string is $$$\mathtt{aaab}$$$. $$$\mathtt{aaab}$$$, $$$\mathtt{aab}$$$ and $$$\mathtt{ab}$$$ are all substrings that are not palindromes, and they have lengths $$$4$$$, $$$3$$$ and $$$2$$$ respectively. Thus, the string is $$$2$$$-good, $$$3$$$-good and $$$4$$$-good. Hence, $$$f(\mathtt{aaab}) = 2 + 3 + 4 = 9$$$.In the second query of the first test case, the string is $$$\mathtt{aaa}$$$. There are no non-palindromic substrings. Hence, $$$f(\mathtt{aaa}) = 0$$$.In the first query of the second test case, the string is $$$\mathtt{abc}$$$. $$$\mathtt{ab}$$$, $$$\mathtt{bc}$$$ and $$$\mathtt{abc}$$$ are all substrings that are not palindromes, and they have lengths $$$2$$$, $$$2$$$ and $$$3$$$ respectively. Thus, the string is $$$2$$$-good and $$$3$$$-good. Hence, $$$f(\mathtt{abc}) = 2 + 3 = 5$$$. Note that even though there are $$$2$$$ non-palindromic substrings of length $$$2$$$, we count it only once.

Sample Inputs:
5
4 4
aaab
1 4
1 3
3 4
2 4
3 2
abc
1 3
1 2
5 4
pqpcc
1 5
4 5
1 3
2 4
2 1
aa
1 2
12 1
steponnopets
1 12

Sample Outputs:
9
0
2
5
5
2
14
0
2
5
0
65

Solution (Python):
import sys, time, random
from collections import deque, Counter, defaultdict
input = lambda : sys.stdin.readline().rstrip()
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
inf = 2 ** 61 - 1
mod = 542577717923

class Rollinghash:

    def __init__(self, string, base, mod):
        n = len(string)
        self.__base = base
        self.__mod = mod
        self.__hash = [0] * (n + 1)
        self.__pow = [1] * (n + 1)
        if isinstance(string, str):
            for (i, c) in enumerate(string):
                o = ord(c) - ord('a') + 1
                self.__hash[i + 1] = (self.__hash[i] * self.__base + o) % self.__mod
                self.__pow[i + 1] = self.__pow[i] * self.__base % self.__mod
        else:
            for (i, c) in enumerate(string):
                o = c
                self.__hash[i + 1] = (self.__hash[i] * self.__base + o) % self.__mod
                self.__pow[i + 1] = self.__pow[i] * self.__base % self.__mod

    def query(self, l, r):
        ret = (self.__hash[r] - self.__hash[l] * self.__pow[r - l]) % self.__mod
        return ret

    def same(self, l1, r1, l2, r2):
        return self.query(l1, r1) == self.query(l2, r2)

def solve():
    (n, q) = mi()
    s = input()
    base = random.randint(0, mod)
    R = Rollinghash(s, base, mod)
    Rrev = Rollinghash(s[::-1], base, mod)

    def is_palindrome(l, r):
        return R.query(l, r) == Rrev.query(n - r, n - l)
    for _ in range(q):
        (l, r) = mi()
        l -= 1
        even = 0
        odd = 0
        for (x, y) in [(l, r), (l, r - 2), (l, r - 1), (l, r - 3), (l + 1, r), (l + 2, r), (l + 3, r)]:
            if l <= x < y <= r and (not is_palindrome(x, y)):
                if (y - x) % 2 == 0 and y - x >= 2:
                    even = max(even, (2 + y - x) * (y - x) // 4)
                elif (y - x) % 2 == 1 and y - x >= 3:
                    odd = max(odd, (3 + y - x) * (y - x - 1) // 4)
        ans = even + odd
        print(ans)
for _ in range(ii()):
    solve()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def manacher(s):
    (i, j) = (0, 0)
    n = len(s)
    ans = [0] * n
    while i < n:
        while i - j >= 0 and i + j < n and (s[i - j] == s[i + j]):
            j += 1
        ans[i] = j
        k = 1
        while i - k >= 0 and k + ans[i - k] < j:
            ans[i + k] = ans[i - k]
            k += 1
        i += k
        j -= k
    return ans
t = int(input())
ans = []
l = 2 * pow(10, 5) + 5
c = [0] * l
for i in range(1, l):
    if not i & 1:
        c[i] = i
for i in range(1, l):
    c[i] += c[i - 1]
for _ in range(t):
    (n, q) = map(int, input().split())
    s = [0] + list(input().rstrip()) + [0]
    r1 = [0] * (n + 1)
    l = 0
    for i in range(1, n + 2):
        if s[l] ^ s[i]:
            for j in range(l, i):
                r1[j] = i - 1
            l = i
    x = [0] * (n + 2)
    for i in range(1, n + 1):
        x[i] = s[i] ^ s[i + 1]
    x[0] = -1
    r2 = [0] * (n + 1)
    l = 0
    for i in range(1, n + 1):
        if x[l] ^ x[i]:
            for j in range(l, i):
                r2[j] = i - 1
            l = i
    s1 = [0] * (2 * n + 3)
    for i in range(1, n + 1):
        s1[2 * i] = s[i]
    p = manacher(s1)
    for _ in range(q):
        (l, r) = map(int, input().split())
        if r <= r1[l]:
            ans0 = 0
        elif r <= r2[l] + 1:
            ans0 = c[r - l + 1]
        else:
            ans0 = (r - l + 1) * (r - l + 2) // 2 - 1
            if r - l + 1 <= p[l + r]:
                ans0 -= r - l + 1
        ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
MOD = 10 ** 9 + 9
b1 = 8675309
b2 = 8675311
MAXN = 210000
pb1 = [1]
for i in range(MAXN):
    pb1.append(b1 * pb1[-1] % MOD)
pb2 = [1]
for i in range(MAXN):
    pb2.append(b2 * pb2[-1] % MOD)

def hashify(s, base):
    out = [0]
    for c in s:
        nex = base * out[-1]
        out.append((nex + ord(c)) % MOD)
    return out

def hashcomp(hasv, i, j):
    out = hasv[j]
    out -= pb1[j - i] * hasv[i]
    return out % MOD

def hashcomp2(h1, h2, i, j):
    out = h1[j]
    out -= pb1[j - i] * h1[i]
    out2 = h2[j]
    out2 -= pb2[j - i] * h2[i]
    out %= MOD
    out2 %= MOD
    return out << 32 | out2
import sys
input = sys.stdin.readline
from collections import Counter
out = []
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    s = input().strip()
    h1 = hashify(s, b1)
    h2 = hashify(s, b2)
    h1r = hashify(s[::-1], b1)
    h2r = hashify(s[::-1], b2)
    l1 = [-1]
    for i in range(1, n):
        if s[i] == s[i - 1]:
            l1.append(l1[i - 1])
        else:
            l1.append(i - 1)
    l2 = [-1, -1]
    for i in range(2, n):
        if s[i] == s[i - 2]:
            l2.append(l2[i - 2])
        else:
            l2.append(i - 2)
    for _ in range(q):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        sz = r - l
        tot = (sz * sz + sz) // 2
        ret = 0
        odd = ((sz + 1) // 2) ** 2
        ev = tot - odd
        odd -= 1
        if l1[r] >= l:
            ret += ev
        if l2[r] >= l or l2[r - 1] >= l:
            ret += odd
        if hashcomp2(h1, h2, l, r + 1) != hashcomp2(h1r, h2r, n - r - 1, n - l):
            ret += sz + 1
        out.append(ret)
print('\n'.join(map(str, out)))