String Hash Queries
Python
Hard
2 views
Problem Description
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.
Sample Test Case
Output:
404084813
756964949
Official Solution
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))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!