n, m = len(T), len(p)

if n < m:

return -1

hash_p, hash_t = 0, 0

for i in range(m):

hash_p = (hash_p * d + ord(p[i])) % q # 计算模式串 p 的哈希值

hash_t = (hash_t * d + ord(T[i])) % q # 计算文本串 T 中第一个子串的哈希值

power = pow(d, m - 1) % q # power 用于移除字符哈希时

for i in range(n - m + 1):

if hash_p == hash_t: # 检查模式串 p 的哈希值和子串的哈希值

match = True # 如果哈希值相等，验证模式串和子串每个字符是否完全相同（避免哈希冲突）

for j in range(m):

if T[i + j] != p[j]:

match = False # 模式串和子串某个字符不相等，验证失败，跳出循环

break

if match: # 如果模式串和子串每个字符是否完全相同，返回匹配开始位置

return i

if i < n - m: # 计算下一个相邻子串的哈希值

hash_t = (hash_t - power * ord(T[i])) % q # 移除字符 T[i]

hash_t = (hash_t * d + ord(T[i + m])) % q # 增加字符 T[i + m]

hash_t = (hash_t + q) % q # 确保 hash_t >= 0