Jimmy loves playing with strings. He thinks string $\mbox{A}$ is similar to string $\mbox{B}$ if the following conditions are satisfied:

Both strings have the same length (i.e., $A=a_{0}a_{1}\ldots a_{n-1}$ and $B=b_0b_1\ldots b_{n-1}$). 
For each valid pair of indices, $(i,j)$, in the strings, $[a_i=a_j$ and $b_i=b_j]$ or $[a_i\neq a_j$ and $b_i\neq b_j]$.  

For example, string $a="adba"$ and $b="bcgb''$ are similar as for $i=0,j=3$, $a[0]==a[3]$ and $b[0]==b[3]$ and for all other $i,j$ pairs $a[i]\neq a[j]$ as well as $b[i]\neq b[j]$.  

He has a string, $\mbox{S}$, of size $n$ and gives you $\textit{q}$ queries to answer where each query is in the form of a pair of integers $(l_i,r_i)$. For each substring $S[l_i,r_i]$, find the number of substrings $S[x,y]$ where substring $S[l_i,r_i]$ is similar to substring $S[x,y]$ and print this number on a new line.

Note: Substring $S[x,y]$ is the contiguous sequence of characters from index $\boldsymbol{x}$ to index $y$. For example, if $S=$ abcdefgh, then $S[3,6]=$ cdef. 

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\textit{q}$. 

The second line contains string $\mbox{S}$. 

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines contains two space-separated integers describing the respective values of $l_i$ and $r_i$ for query $\boldsymbol{i}$.

Constraints

$1\leq n,q\leq5\times10^4$
$1\leq L_i\leq R_i\leq n$
$s_i\in\{a,b,c,d,e,f,g,h,i,j\}$

Output Format

For each query, print the number of similar substrings on a new line.

Sample Input
8 4
giggabaj
1 1
1 2
1 3
2 4

Sample Output
8
6
2
1

Explanation

We perform the following sequence of queries:

Strings with length $1$ are all similar, so our answer is $8$.
gi, ig, ga, ab, ba, and aj are similar, so our answer is $6$.
gig and aba are similar, so our answer is $2$.
igg has no similar string, so our answer is $1$.

Source: hackerrank | Difficulty: HARD
Tags: String algorithms


Solutions:
import sys
import itertools as it
import time
(q, n) = [int(m) for m in input().strip().split()]
S = input().strip()
Cases = []
for i in range(n):
	Cases.append([int(m) for m in input().strip().split()])
CompDict = {}
MaxSize = 0
for C in Cases:
	Size = C[1] - C[0] + 1
	MaxSize = max([MaxSize, Size])
MaxPrecomp = 5
MaxBin = min([MaxPrecomp, MaxSize])
BinLoc = [[] for m in range(MaxBin)]
BinLoc[0] = [0 for m in range(q)]
BinCount = [{} for m in range(MaxBin)]
IndexBins = [{} for m in range(MaxBin)]
MaxPowerList = 1
for Width in range(2, MaxBin + 1):
	PowerList = [2 ** m * MaxPowerList for m in range(Width - 1)]
	MaxPowerList = PowerList[-1] * 2
	for StartInd in range(q - Width + 1):
		BinVal = BinLoc[Width - 2][StartInd]
		CheckInd2 = Width - 1
		for (C1, CheckInd1) in enumerate(range(Width - 1)):
			TupLoc = (StartInd + CheckInd1, StartInd + CheckInd2)
			try:
				CompVal = CompDict[TupLoc]
			except:
				CompDict[TupLoc] = S[TupLoc[0]] == S[TupLoc[1]]
				CompVal = CompDict[TupLoc]
			if CompVal:
				BinVal += PowerList[C1]
		BinLoc[Width - 1].append(BinVal)
		try:
			BinCount[Width - 1][BinVal] += 1
			IndexBins[Width - 1][BinVal].append(StartInd)
		except:
			BinCount[Width - 1][BinVal] = 1
			IndexBins[Width - 1][BinVal] = [StartInd]
SolnList = [None for m in range(n)]
for (cInd, C) in enumerate(Cases):
	StartPy = C[0] - 1
	FrameLen = C[1] - C[0] + 1
	if FrameLen == 1:
		SolnList[cInd] = q
	elif FrameLen <= MaxPrecomp:
		SolnList[cInd] = BinCount[FrameLen - 1][BinLoc[FrameLen - 1][StartPy]]
	else:
		Count = 0
		SrefNorm = ''
		for i in IndexBins[MaxBin - 1][BinLoc[MaxBin - 1][StartPy]]:
			if i == StartPy:
				Count += 1
			elif i + FrameLen <= q:
				ExcessFrame = (FrameLen - 1) % (MaxBin - 1) + 1
				nMaxBinFrames = int((FrameLen - ExcessFrame) / (MaxBin - 1))
				Match = True
				for j in range(1, nMaxBinFrames):
					if not BinLoc[MaxBin - 1][StartPy + j * (MaxBin - 1)] == BinLoc[MaxBin - 1][i + j * (MaxBin - 1)]:
						Match = False
						break
				if Match:
					Match = BinLoc[ExcessFrame - 1][StartPy + nMaxBinFrames * (MaxBin - 1)] == BinLoc[ExcessFrame - 1][i + nMaxBinFrames * (MaxBin - 1)]
				if Match:
					if SrefNorm == '':
						Sref = S[StartPy:StartPy + FrameLen]
						CharMap = {}
						SrefNorm = ''
						CurrentChr = 97
						for Char in Sref:
							try:
								SrefNorm += CharMap[Char]
							except:
								CharMap[Char] = chr(CurrentChr)
								CurrentChr += 1
								SrefNorm += CharMap[Char]
					Si = S[i:i + FrameLen]
					CharMap = {}
					SiNorm = ''
					CurrentChr = 97
					for Char in Si:
						try:
							SiNorm += CharMap[Char]
						except:
							CharMap[Char] = chr(CurrentChr)
							CurrentChr += 1
							SiNorm += CharMap[Char]
					if SiNorm != SrefNorm:
						Match = False
				if Match:
					Count += 1
		SolnList[cInd] = Count
for i in SolnList:
	print(i)


import os
import sys

def calc_fingerprint(s):
	dict = {s[0]: 0}
	fingerprint = '0'
	j = 1
	for i in range(1, len(s)):
		if s[i] not in dict:
			(dict[s[i]], j) = (j, j + 1)
		fingerprint += str(dict[s[i]])
	return int(fingerprint)
fingerprints = []

def naive_check(s, a, b):
	s1 = s[a - 1:b]
	k = 0
	for i in range(len(s) - (b - a)):
		if b - a > 9 and fingerprints[a - 1] != fingerprints[i]:
			continue
		dict = {}
		s2 = s[i:i + (b - a) + 1]
		for i in range(b - a + 1):
			if s2[i] not in dict:
				if s1[i] in dict.values():
					break
				dict[s2[i]] = s1[i]
			if dict[s2[i]] != s1[i]:
				break
		else:
			k += 1
	return k
(n, q) = map(int, input().split())
s = input()
if len(s) > 10:
	for i in range(0, len(s) - 10):
		fingerprints.append(calc_fingerprint(s[i:i + 10]))
for _ in range(q):
	(a, b) = map(int, input().rstrip().split())
	print(naive_check(s, a, b))


import sys
import itertools as it
import time
(q, n) = [int(m) for m in input().strip().split()]
S = input().strip()
Cases = []
for i in range(n):
	Cases.append([int(m) for m in input().strip().split()])
CompDict = {}
MaxSize = 0
for C in Cases:
	Size = C[1] - C[0] + 1
	MaxSize = max([MaxSize, Size])
MaxPrecomp = 5
MaxBin = min([MaxPrecomp, MaxSize])
BinLoc = [[] for m in range(MaxBin)]
BinLoc[0] = [0 for m in range(q)]
BinCount = [{} for m in range(MaxBin)]
IndexBins = [{} for m in range(MaxBin)]
MaxPowerList = 1
for Width in range(2, MaxBin + 1):
	PowerList = [2 ** m * MaxPowerList for m in range(Width - 1)]
	MaxPowerList = PowerList[-1] * 2
	for StartInd in range(q - Width + 1):
		BinVal = BinLoc[Width - 2][StartInd]
		CheckInd2 = Width - 1
		for (C1, CheckInd1) in enumerate(range(Width - 1)):
			TupLoc = (StartInd + CheckInd1, StartInd + CheckInd2)
			try:
				CompVal = CompDict[TupLoc]
			except:
				CompDict[TupLoc] = S[TupLoc[0]] == S[TupLoc[1]]
				CompVal = CompDict[TupLoc]
			if CompVal:
				BinVal += PowerList[C1]
		BinLoc[Width - 1].append(BinVal)
		try:
			BinCount[Width - 1][BinVal] += 1
			IndexBins[Width - 1][BinVal].append(StartInd)
		except:
			BinCount[Width - 1][BinVal] = 1
			IndexBins[Width - 1][BinVal] = [StartInd]
SolnList = [None for m in range(n)]
for (cInd, C) in enumerate(Cases):
	StartPy = C[0] - 1
	FrameLen = C[1] - C[0] + 1
	if FrameLen == 1:
		SolnList[cInd] = q
	elif FrameLen <= MaxPrecomp:
		SolnList[cInd] = BinCount[FrameLen - 1][BinLoc[FrameLen - 1][StartPy]]
	else:
		Count = 0
		SrefNorm = ''
		for i in IndexBins[MaxBin - 1][BinLoc[MaxBin - 1][StartPy]]:
			if i == StartPy:
				Count += 1
			elif i + FrameLen <= q:
				ExcessFrame = (FrameLen - 1) % (MaxBin - 1) + 1
				nMaxBinFrames = int((FrameLen - ExcessFrame) / (MaxBin - 1))
				Match = True
				for j in range(1, nMaxBinFrames):
					if not BinLoc[MaxBin - 1][StartPy + j * (MaxBin - 1)] == BinLoc[MaxBin - 1][i + j * (MaxBin - 1)]:
						Match = False
						break
				if Match:
					Match = BinLoc[ExcessFrame - 1][StartPy + nMaxBinFrames * (MaxBin - 1)] == BinLoc[ExcessFrame - 1][i + nMaxBinFrames * (MaxBin - 1)]
				if Match:
					if SrefNorm == '':
						Sref = S[StartPy:StartPy + FrameLen]
						CharMap = {}
						SrefNorm = ''
						CurrentChr = 97
						for Char in Sref:
							try:
								SrefNorm += CharMap[Char]
							except:
								CharMap[Char] = chr(CurrentChr)
								CurrentChr += 1
								SrefNorm += CharMap[Char]
					Si = S[i:i + FrameLen]
					CharMap = {}
					SiNorm = ''
					CurrentChr = 97
					for Char in Si:
						try:
							SiNorm += CharMap[Char]
						except:
							CharMap[Char] = chr(CurrentChr)
							CurrentChr += 1
							SiNorm += CharMap[Char]
					if SiNorm != SrefNorm:
						Match = False
				if Match:
					Count += 1
		SolnList[cInd] = Count
for i in SolnList:
	print(i)


import sys
import itertools as it
import time
(q, n) = [int(m) for m in input().strip().split()]
S = input().strip()
outcomes = []
for i in range(n):
	outcomes.append([int(m) for m in input().strip().split()])
my_dict = {}
maximumsize = 0
for C in outcomes:
	Size = C[1] - C[0] + 1
	maximumsize = max([maximumsize, Size])
maximumprecomp = 5
maxibhai = min([maximumprecomp, maximumsize])
binbhai = [[] for m in range(maxibhai)]
binbhai[0] = [0 for m in range(q)]
binginti = [{} for m in range(maxibhai)]
index_bins = [{} for m in range(maxibhai)]
MaxPowerList = 1
for Width in range(2, maxibhai + 1):
	PowerList = [2 ** m * MaxPowerList for m in range(Width - 1)]
	MaxPowerList = PowerList[-1] * 2
	for StartInd in range(q - Width + 1):
		BinVal = binbhai[Width - 2][StartInd]
		CheckInd2 = Width - 1
		for (C1, CheckInd1) in enumerate(range(Width - 1)):
			TupLoc = (StartInd + CheckInd1, StartInd + CheckInd2)
			try:
				CompVal = my_dict[TupLoc]
			except:
				my_dict[TupLoc] = S[TupLoc[0]] == S[TupLoc[1]]
				CompVal = my_dict[TupLoc]
			if CompVal:
				BinVal += PowerList[C1]
		binbhai[Width - 1].append(BinVal)
		try:
			binginti[Width - 1][BinVal] += 1
			index_bins[Width - 1][BinVal].append(StartInd)
		except:
			binginti[Width - 1][BinVal] = 1
			index_bins[Width - 1][BinVal] = [StartInd]
SolnList = [None for m in range(n)]
for (cInd, C) in enumerate(outcomes):
	StartPy = C[0] - 1
	FrameLen = C[1] - C[0] + 1
	if FrameLen == 1:
		SolnList[cInd] = q
	elif FrameLen <= maximumprecomp:
		SolnList[cInd] = binginti[FrameLen - 1][binbhai[FrameLen - 1][StartPy]]
	else:
		Count = 0
		SrefNorm = ''
		for i in index_bins[maxibhai - 1][binbhai[maxibhai - 1][StartPy]]:
			if i == StartPy:
				Count += 1
			elif i + FrameLen <= q:
				ExcessFrame = (FrameLen - 1) % (maxibhai - 1) + 1
				nmaxibhaiFrames = int((FrameLen - ExcessFrame) / (maxibhai - 1))
				Match = True
				for j in range(1, nmaxibhaiFrames):
					if not binbhai[maxibhai - 1][StartPy + j * (maxibhai - 1)] == binbhai[maxibhai - 1][i + j * (maxibhai - 1)]:
						Match = False
						break
				if Match:
					Match = binbhai[ExcessFrame - 1][StartPy + nmaxibhaiFrames * (maxibhai - 1)] == binbhai[ExcessFrame - 1][i + nmaxibhaiFrames * (maxibhai - 1)]
				if Match:
					if SrefNorm == '':
						Sref = S[StartPy:StartPy + FrameLen]
						CharMap = {}
						SrefNorm = ''
						CurrentChr = 97
						for Char in Sref:
							try:
								SrefNorm += CharMap[Char]
							except:
								CharMap[Char] = chr(CurrentChr)
								CurrentChr += 1
								SrefNorm += CharMap[Char]
					Si = S[i:i + FrameLen]
					CharMap = {}
					SiNorm = ''
					CurrentChr = 97
					for Char in Si:
						try:
							SiNorm += CharMap[Char]
						except:
							CharMap[Char] = chr(CurrentChr)
							CurrentChr += 1
							SiNorm += CharMap[Char]
					if SiNorm != SrefNorm:
						Match = False
				if Match:
					Count += 1
		SolnList[cInd] = Count
for i in SolnList:
	print(i)


import sys
import itertools as it
import time
(q, n) = [int(m) for m in input().strip().split()]
S = input().strip()
outcomes = []
for i in range(n):
	outcomes.append([int(m) for m in input().strip().split()])
my_dict = {}
maximumsize = 0
for C in outcomes:
	Size = C[1] - C[0] + 1
	maximumsize = max([maximumsize, Size])
maximumprecomp = 5
maxibhai = min([maximumprecomp, maximumsize])
binbhai = [[] for m in range(maxibhai)]
binbhai[0] = [0 for m in range(q)]
binginti = [{} for m in range(maxibhai)]
index_bins = [{} for m in range(maxibhai)]
MaxPowerList = 1
for Width in range(2, maxibhai + 1):
	PowerList = [2 ** m * MaxPowerList for m in range(Width - 1)]
	MaxPowerList = PowerList[-1] * 2
	for StartInd in range(q - Width + 1):
		BinVal = binbhai[Width - 2][StartInd]
		CheckInd2 = Width - 1
		for (C1, CheckInd1) in enumerate(range(Width - 1)):
			TupLoc = (StartInd + CheckInd1, StartInd + CheckInd2)
			try:
				CompVal = my_dict[TupLoc]
			except:
				my_dict[TupLoc] = S[TupLoc[0]] == S[TupLoc[1]]
				CompVal = my_dict[TupLoc]
			if CompVal:
				BinVal += PowerList[C1]
		binbhai[Width - 1].append(BinVal)
		try:
			binginti[Width - 1][BinVal] += 1
			index_bins[Width - 1][BinVal].append(StartInd)
		except:
			binginti[Width - 1][BinVal] = 1
			index_bins[Width - 1][BinVal] = [StartInd]
SolnList = [None for m in range(n)]
for (cInd, C) in enumerate(outcomes):
	StartPy = C[0] - 1
	FrameLen = C[1] - C[0] + 1
	if FrameLen == 1:
		SolnList[cInd] = q
	elif FrameLen <= maximumprecomp:
		SolnList[cInd] = binginti[FrameLen - 1][binbhai[FrameLen - 1][StartPy]]
	else:
		Count = 0
		SrefNorm = ''
		for i in index_bins[maxibhai - 1][binbhai[maxibhai - 1][StartPy]]:
			if i == StartPy:
				Count += 1
			elif i + FrameLen <= q:
				ExcessFrame = (FrameLen - 1) % (maxibhai - 1) + 1
				nmaxibhaiFrames = int((FrameLen - ExcessFrame) / (maxibhai - 1))
				Match = True
				for j in range(1, nmaxibhaiFrames):
					if not binbhai[maxibhai - 1][StartPy + j * (maxibhai - 1)] == binbhai[maxibhai - 1][i + j * (maxibhai - 1)]:
						Match = False
						break
				if Match:
					Match = binbhai[ExcessFrame - 1][StartPy + nmaxibhaiFrames * (maxibhai - 1)] == binbhai[ExcessFrame - 1][i + nmaxibhaiFrames * (maxibhai - 1)]
				if Match:
					if SrefNorm == '':
						Sref = S[StartPy:StartPy + FrameLen]
						CharMap = {}
						SrefNorm = ''
						CurrentChr = 97
						for Char in Sref:
							try:
								SrefNorm += CharMap[Char]
							except:
								CharMap[Char] = chr(CurrentChr)
								CurrentChr += 1
								SrefNorm += CharMap[Char]
					Si = S[i:i + FrameLen]
					CharMap = {}
					SiNorm = ''
					CurrentChr = 97
					for Char in Si:
						try:
							SiNorm += CharMap[Char]
						except:
							CharMap[Char] = chr(CurrentChr)
							CurrentChr += 1
							SiNorm += CharMap[Char]
					if SiNorm != SrefNorm:
						Match = False
				if Match:
					Count += 1
		SolnList[cInd] = Count
for i in SolnList:
	print(i)