字符串哈希

1
2
3
4
5
6
7
8
9
from collections import defaultdict
dict=defaultdict(int)
n=int(input())
for i in range(n):
    x=input()
    dict[x]+=1
print(len(dict))
        
#此方法可以同时处理str和int
1
2
3
4
5
6
7
8
#直接调用hash函数
n=input()
h=[]
for i in range(n):
    x=input()
    if hash(x) not in h:
        h.append(hash(x))
print(len(x))

Manacher算法

理解回文半径数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def manacher(self):
        s = '#' + '#'.join(self) + '#' # 字符串处理，用特殊字符隔离字符串，方便处理偶数子串
        lens = len(s)
        p = [0] * lens            # p[i]表示i作中心的最长回文子串的半径，初始化p[i]
        mx = 0                    # 之前最长回文子串的右边界
        id = 0                    # 之前最长回文子串的中心位置
        for i in range(lens):     # 遍历字符串
            if mx > i:
                p[i] = min(mx-i, p[int(2*id-i)]) #由理论分析得到
            else :                # mx <= i
                p[i] = 1
            while i-p[i] >= 0 and i+p[i] < lens and s[i-p[i]] == s[i+p[i]]:  # 满足回文条件的情况下
                p[i] += 1  # 两边扩展
            if(i+p[i]) > mx:  # 新子串右边界超过了之前最长子串右边界
                mx, id = i+p[i], i # 移动之前最长回文子串的中心位置和边界，继续向右匹配
        i_res = p.index(max(p)) # 获取最终最长子串中心位置
        s_res = s[i_res-(p[i_res]-1):i_res+p[i_res]] #获取最终最长子串，带"#"
        return max(p)-1  #返回最长回文子串（去掉"#"）和它的长度

字典树

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
26
27
28
29
30
31
32
class Node:
    __slots__ = 'son', 'end'

    def __init__(self):
        self.son = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def find(self, word: str) -> int:
        cur = self.root
        for c in word:
            if c not in cur.son:
                return 0
            cur = cur.son[c]
        return 2 if cur.end else 1

    def search(self, word: str) -> bool:
        return self.find(word) == 2

    def startsWith(self, prefix: str) -> bool:
        return self.find(prefix) != 0