String Hashing (Տողի Հեշավորում)

Տողի հեշավորման բազմաթիվ մեթոդներ կան, սակայն այս բաժնում կքննարկենք ամենատարածված և ներդրման տեսանկյունից ինտուիտիվ տարբերակներից մեկը: Այն լայնորեն օգտագործվում է τόσο մրցութային ծրագրավորման ընթացքում, όσο էլ ալգորիթմական հարցազրույցներում:

Երևակայենք, որ տրված է տող s, որը բաղկացած է տառերից : Մեր նպատակն է ունենալ մի մեթոդ, որի միջոցով հարկ եղած դեպքում հեշտ կլինի հաշվել տողի կամայական շարունակական ենթատողի հեշտ (hash) արժեքը:

Ուժեղ Հեշ Ֆունկցիայի Ընտրություն

Օրինակներից մեկը, որը լավ է աշխատում գործնականում, այն ֆունկցիան է, որն ամփոփում է (hash) տողը, յուրաքանչյուր սիմվոլի (թվային արժեքը) բազմապատկելով որևէ պարզ թվի աստիճանով և արդյունքը վերցնելով m-ով:

Այստեղ և՛ p-ն, և՛ m-ն պետք է ընտրվեն որպես պարզ թվեր: Օրինակ՝ p-ն կարելի է վերցնել 1997, 127 և այլն, իսկ m-ն, քանզի որքան մեծ է այն, այնքան նվազում է բախումների հավանականությունը: Այնուամենայնիվ, m-ի չափազանց մեծ արժեքը կարող է դանդաղեցնել հաշվարկները: Շատ իրագործումներում m ընտրվում է կամ : Ստորև բերված է դրա իրագործման տարբերակը (կոդի մեջ չենք թարգմանում, միայն մեկնաբանություններն են թարգմանված).

s = input()                                  # Օգտատիրոջ կողմից մուտքագրվող կամայական երկարության տող
p = 1997                                     # p: պարզ թիվ
m = 1_000_000_007                            # m: բավականաչափ մեծ պարզ թիվ

h = [0] * (len(s) + 1)                       # նախապես լցնել h-ը 0-ներով
for i in range(len(s)):
    h[i + 1] = h[i] + ord(s[i])              # Գումարել текուщее սիմվոլը
    h[i + 1] *= p                            # Բոլոր p-ի աստիճանները բարձրացնել 1-ով
    h[i + 1] %= m                            # Յուրաքանչյուր քայլից հետո սպասարկել mod m

Այստեղ ներդրվում է գլորվող հեշի գաղափարը (նման է prefix sum-ի գաղափարին).

Ուշադրություն դարձրեք, որ այստեղ h զանգվածի առաջին ինդեքսը (h_0) «կեղծ» է և հավասար է 0-ի: Բացի դրանից, կարելի է նկատել, որ ամեն հաջորդ h-ի արժեքը կախված է նախորդից:

Հեշի Հաշվարկը Տողի Կամայական Ենթատողի Համար

Ենթադրենք ուզում ենք համեմատել երկու ենթատող s[l1; r1) և s[l2; r2), որոնք ունեն նույն երկարությունը, և ստուգել՝ արդյոք նույնն են: Կցանկանայինք ստանալ «նորմավորված» հեշ ամեն ենթատողի համար: Եթե այդ հեշերը ստացվեն հավասար, կընդունենք, որ ենթատողերը հավասար են:

Այժմ, երբ ունենք h հեշ-զանգվածը, տեսականորեն կարող ենք պարզ ձև으로 հաշվել s[l; r) ենթատողի հեշը, սակայն միայն աջ և ձախ ինդեքսների տարբերությունն առնելը բավարար չէ:

Ենթադրենք ունենք ձախ ինդեքս l և աջ ինդեքս r, և ցանկանում ենք հաշվել s[l; r) ենթատողի հեշը: Իդեալական տարբերակում, արդյունքը պետք է զուգակցվի այն հեշին, որը կստանայինք, եթե նույն ենթատողի համար հաշվում էինք ամեն ինչ նորից: Քանի որ յուրաքանչյուր սիմվոլ բազմապատկվում է պարզ թվի աստիճանով, պետք է համապատասխանորեն հարմարեցնել ձախ կողմը r-ի և l-ի տարբերությամբ:

Սա ճիշտ նույն արժեքն է, ինչ ստացվում է, երբ առանձին հաշվում ենք s[l; r) տողի հեշը: Շեշտենք, որ այստեղ առաջին սիմվոլը բազմապատկվում է p^{r-l}-ով, որն էլ հենց ենթատողի երկարության աստիճանն է, իսկ վերջինը p^1-ով, ինչը համընկնում է լիարժեք տողի հեշի տրամաբանությանը:

Սա ապահովում է, որ տարբեր ենթատողեր, ինչպիսիք են [1; 5) և [4; 8), եթե ունեն նույն սիմվոլները, ստանան նույն հեշը, անկախ նրանից, թե թեորետիկ «ամենասկզբից» քանիրդ աստիճաններից ենք սկսել բազմապատկել: Դա կարելի է իրականացնել հետևյալ ձևով, պարզապես հարմարեցնելով h[l] արժեքը:

# Precompute the powers
pows = [1] * (len(s) + 1)                  # նախահաշվել p-ի բոլոր աստիճանները
for i in range(len(s)):                    # p^i = p^(i-1) * p
    pows[i + 1] = pows[i] * p
    pows[i + 1] %= m

# [l; r) հատվածի հեշը հաշվել O(1)-ում
res = h[r] - h[l] * pows[r - l]            # h[l]-ը աճեցնել (r-l) աստիճանով
res %= m
print(res)

Եթե օրինակ s-ը hello hellyo է, ապա h և pows զանգվածները կունենան հետևյալ արժեքները, և որոշ հարցումներ կատարելու դեպքում կունենանք հետևյալ արդյունքները.

# s ->     h       e          l          l          o                     h          e          l          l          y          o
h    = [0, 207688, 414954633, 664611981, 230332444, 974109122, 295966923, 46148782,  159318707, 159671329, 863857463, 123583173, 795816426]
pows = [1, 1997,   3988009,   964053924, 215672753, 698484731, 873998049, 374091638, 60995857,  808725582, 24975949,  876969810, 308698313]
# i ->  0  1       2          3          4          5          6          7          8          9          10         11         12

# hash for s[0: 3] (hel)    -> 664611981   (l = 0, r = 3)
# hash for s[6: 9] (hel)    -> 664611981   (l = 6, r = 9)
# hash for s[0: 5] (hello)  -> 974109122   (l = 0, r = 5)
# hash for s[6: 11] (helly) -> 974129092   (l = 6, r = 11)

Պատրաստ եք հեշավորել տողը ևտարբեր հարցումներին պատասխանել, թե ինչ հեշ է ստացվում կոնկրետ ենթատողի համար?

Մուտք

Մուտքի առաջին տողում տրված է տողը s (1 ≤ |s| ≤ ):

Երկրորդ տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 100000), որն արտահայտում է հարցումների քանակը:

Հաջորդ q տողերը պարունակում են զույգ ինդեքսներ (0 ≤ ≤ |s|):

Ելք

Ծրագիրը պետք է տպի հատվածի հեշը:

Օրինակ