First Window with a Given Fingerprint

Hard

Every lowercase English letter has a weight: a is 1, b is 2, …, z is 26. The fingerprint of a string w of length L with base base and modulus mod is (weight(w[0])·base⁰ + weight(w[1])·base¹ + ... + weight(w[L − 1])·base^(L − 1)) mod mod. You are given a string text and numbers base, mod, length and fingerprint. Find the leftmost substring of text (a contiguous piece) of length length whose fingerprint equals fingerprint, and return it. Such a substring is guaranteed to exist.

Example 1

text='bad', base=10, mod=100, length=2, fingerprint=12 → 'ba'

The fingerprint of "ba" is 2·1 + 1·10 = 12, a match right away. "ad" would give 1 + 4·10 = 41.

Example 2

text='zebra', base=5, mod=9, length=2, fingerprint=6 → 'ze'

"ze": 26 + 5·5 = 51, and 51 mod 9 = 6. "eb" also has fingerprint 6 (5 + 2·5 = 15), but "ze" comes first.

Example 3

text='hello', base=3, mod=10, length=3, fingerprint=3 → 'llo'

"hel": 8 + 5·3 + 12·9 = 131 → 1; "ell": 5 + 12·3 + 12·9 = 149 → 9; "llo": 12 + 12·3 + 15·9 = 183 → 3.

Constraints

1 ≤ length ≤ text.length ≤ 2·10⁴
1 ≤ base, mod < 2³¹
0 ≤ fingerprint < mod
text consists of lowercase English letters only
An answer always exists

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Sliding Window Hash Function Rolling Hash