D22-读论文D22&算法D22

841字符串哈希

用p数组储存进制信息
用s数组储存字符串哈希相关信息
用getHash获取字符串中某一段的哈希值

n,m  = map(int, input().split())
string = ' '+ str(input())
N = 100010
P,Q = 131, 2**64
p,s = [0]*N, [0]*N

p[0] = 1
for i in range(1, 1+n):
    # p用来计算p的n次方，%Q以免溢出
    p[i] = p[i-1]*P%Q
    # s用来储存长度为i的字符串的哈希值
    s[i] = (s[i-1]*P + ord(string[i]))%Q


def getHash(l,r):
    return (s[r]-s[l-1]*p[r-l+1])%Q

for _ in range(m):
    l1, r1, l2, r2 = map(int,input().split())
    if getHash(l1,r1)==getHash(l2,r2):
        print('Yes')
    else:
        print('No')
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

840模拟散列表

n = int(input())

N = 100010
null = 0x3f3f3f3f
s = [null]*N
# find返回的要不然是空值，要不然是x已经存在；
# 对于插入，都直接放入即可；对于判断是否出现过，则判断该位置的值是否为x。
def find(x):
    k = x%N
    while s[k]!=null and s[k]!=x:
        k += 1
        if k==N:
            k=0
    return k

for _ in range(n):
    op, pt = input().split()
    x = int(pt)
    if op=='I':
        s[find(x)] = x
    else:
        if s[find(x)]==x:
            print('Yes')
        else:
            print('No')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25