String Hash Queries
Hard
Python
Functions
13 views
Problem Statement
Read a string s (lowercase) and q queries l r (1-based). Use helper function to build prefix hashes and answer hash values mod 1000000007.
Input Format
Line1: s. Line2: q. Next q lines: l r.
Output Format
q lines hash.
Example
abcd 2 1 2 2 4
404084813 756964949
Constraints
len(s),q
Input / Output Format
Input Format
Line1: s. Line2: q. Next q lines: l r.
Output Format
q lines hash.
Constraints
len(s),q
Examples
Input:
abcd
2
1 2
2 4
Output:
404084813
756964949
Example Solution (Public)
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
q=int(lines[1].strip())
MOD=1000000007
BASE=911382323
n=len(s)
def build_hash(t):
pref=[0]*(len(t)+1)
pows=[1]*(len(t)+1)
for i,ch in enumerate(t, start=1):
pref[i]=(pref[i-1]*BASE + (ord(ch)-96))%MOD
pows[i]=(pows[i-1]*BASE)%MOD
return pref,pows
def get_hash(pref,pows,l,r):
return (pref[r] - pref[l-1]*pows[r-l+1])%MOD
pref,pows=build_hash(s)
out=[]
for i in range(q):
l,r=map(int,(lines[2+i] if 2+i<len(lines) else '1 1').split())
out.append(str(get_hash(pref,pows,l,r)))
sys.stdout.write('\
'.join(out))
Official Solution Code
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
q=int(lines[1].strip())
MOD=1000000007
BASE=911382323
n=len(s)
def build_hash(t):
pref=[0]*(len(t)+1)
pows=[1]*(len(t)+1)
for i,ch in enumerate(t, start=1):
pref[i]=(pref[i-1]*BASE + (ord(ch)-96))%MOD
pows[i]=(pows[i-1]*BASE)%MOD
return pref,pows
def get_hash(pref,pows,l,r):
return (pref[r] - pref[l-1]*pows[r-l+1])%MOD
pref,pows=build_hash(s)
out=[]
for i in range(q):
l,r=map(int,(lines[2+i] if 2+i<len(lines) else '1 1').split())
out.append(str(get_hash(pref,pows,l,r)))
sys.stdout.write('\
'.join(out))
Please login to submit solutions.