2023年7月20日发(作者：)

⼒扣--字符串中常见经典算法 线性存储的⼀组数据（默认为字符）。包括⼀些特殊的操作集：求串的长度⽐较两串是否相等两串相接求⼦串插⼊⼦串匹配⼦串删除⼦串算法其中图⽚中的match就是next，叫法不同。匹配图解：python代码：class Solution: # 获取next数组 def get_next(self, T): i = 0 j = -1 next_val = [-1] * len(T) while i < len(T)-1: if j == -1 or T[i] == T[j]: i += 1 j += 1 # next_val[i] = j if i < len(T) and T[i] != T[j]: next_val[i] = j else: next_val[i] = next_val[j] else: j = next_val[j] return next_val # KMP算法 def kmp(self, S, T): i = 0 j = 0 next = _next(T) while i < len(S) and j < len(T): if j == -1 or S[i] == T[j]: i += 1 j += 1 else: j = next[j] if j == len(T): return i - j else: return -1if __name__ == '__main__': haystack = 'acabaabaabcacaabc' needle = 'abaabcac' s = Solution() print((haystack, needle)) # 输出 "5"2.替换空格 涉及到的⼒扣题⽬为：剑指 Offer 05.替换空格3.最长公共前缀 涉及到的⼒扣题⽬为：14. 最长公共前缀4.回⽂串（1）最长回⽂串 涉及到的⼒扣题⽬为：409.最长回⽂串（2）验证回⽂串 涉及到的⼒扣题⽬为：（3）最长回⽂⼦串 涉及到的⼒扣题⽬为：（4）最长回⽂⼦序列 涉及到的⼒扣题⽬为：516. 最长回⽂⼦序列5.括号匹配深度 涉及到的⼒扣题⽬为：

6.把字符串转换为整数 涉及到的⼒扣题⽬为：剑指offer67.把字符串转换为整数