Queries for Number of Palindromes (Codeforces 245H)
Tags: DP, hashing

You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.

Input: The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.It is guaranteed that the given string consists only of lowercase English letters.

Output: Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Note: Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».

Sample Inputs:
caaaba
5
1 1
1 4
2 3
4 6
4 5

Sample Outputs:
1
7
3
4
2

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def primes(n):
    ans = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            while n % i == 0:
                n //= i
        if n == 1:
            break
    if n != 1:
        ans.append(n)
    return ans

def countSetBits(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

def factors(n):
    ans = []
    rev = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i * i == n:
                ans.append(i)
                continue
            ans.append(i)
            rev.append(n // i)
    return ans + rev[::-1]

def factorial(x, mod):
    if x == 1 or x == 0 or x >= mod:
        return 1
    ans = 1
    for i in range(2, x + 1):
        ans *= i
        if ans % mod == 0:
            return 0
        ans %= mod
    return ans
    return x % mod * factorial(x - 1, mod) % mod
s = input()
q = int(input())
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i] = 1
for i in range(n - 1):
    if s[i] == s[i + 1]:
        dp[i][i + 1] = 1
for l in range(3, n + 1):
    for start in range(n + 1 - l):
        end = start + l - 1
        if s[start] == s[end] and dp[start + 1][end - 1]:
            dp[start][end] = 1
for i in range(n - 1):
    for j in range(i + 1, n):
        dp[i][j] += dp[i][j - 1]
for j in range(1, n):
    for i in range(j - 1, -1, -1):
        dp[i][j] += dp[i + 1][j]
for i in range(q):
    [l, r] = list(map(int, input().split()))
    l -= 1
    r -= 1
    ans = dp[l][r]
    print(ans)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

def main():
    s = input()
    n = len(s)
    pl = [[0] * n for _ in range(n + 1)]
    dp = [[0] * n for _ in range(n + 1)]
    for i in range(n):
        pl[i][i] = dp[i][i] = 1
        pl[i + 1][i] = 1
    for ln in range(2, n + 1):
        for st in range(n - ln + 1):
            j = st + ln - 1
            if ln == 0:
                pl[i][j] = 1
            elif s[st] == s[j]:
                if ln == 1:
                    pl[i][j] = 1
                else:
                    pl[st][j] = pl[st + 1][j - 1]
            else:
                pl[st][j] = int(s[st] == s[j] and pl[st + 1][j - 1])
    for ln in range(2, n + 1):
        for st in range(n - ln + 1):
            dp[st][st + ln - 1] = dp[st][st + ln - 2] + dp[st + 1][st + ln - 1] - dp[st + 1][st + ln - 2] + pl[st][st + ln - 1]
    for _ in range(int(input())):
        (l, r) = map(int, input().split())
        print(dp[l - 1][r - 1])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for t in range(1):
        main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

def main():
    s = input()
    n = len(s)
    palin = [[0 for _ in range(n)] for _ in range(n)]
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for sz in range(n):
        for i in range(n - sz):
            j = i + sz
            if sz == 0:
                palin[i][j] = 1
            elif s[i] == s[j]:
                if sz == 1:
                    palin[i][j] = 1
                else:
                    palin[i][j] = palin[i + 1][j - 1]
            else:
                palin[i][j] = int(s[i] == s[j] and palin[i + 1][j - 1])
    for sz in range(n):
        for i in range(n - sz):
            j = i + sz
            if sz == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + palin[i][j]
    for _ in range(int(input())):
        (l, r) = list(map(int, input().split()))
        print(dp[l - 1][r - 1])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for t in range(1):
        main()