Casshern - 个人主页动态 - 牛客网

发布(2) 评论刷题收藏

2022-05-06 04:51

已编辑

National University of Singapore 算法工程师

题解 | #查找两个字符串a,b中的最长公共子串#

二分搜索+滚动哈希 输入的两个串s1，s2。 为了满足题目要求，不妨保持s2为较短的那一个。 先用二分搜索找到一个长度mid，然后用滚动哈希的映射值搜索两个串是否存在长度等于mid的公共子串。滚动哈希，先扫描s1定长的所有子串映射为一个个数值，将其保存在set中。当之后s2有其他子串的映射值等于set中的某值的话，那么该子串为长度等于mid的公共子串。（当然，滚动哈希有可能匹配失败，对于该题是够用的，不放心的话再可以手动写一个验证） 由于先扫描了s1，那么再搜索s2（较短串）时只要找到重复的子串，直接储存子串的长度和起始位置即可 最后二分法会找到一个最长的子串长度，并且储存了在s2中该子串的起...

0 点赞评论收藏

分享

2022-05-06 04:06

National University of Singapore 算法工程师

题解 | #公共子串计算#

看了下题解里好像没太有人用这个，二分法+滚动哈希 P,Q=131,2**64 s1=input() s2=input() n1,n2=len(s1),len(s2) def hsm(mid): seen=set() K=P**mid%Q pre=0 for i in range(mid): pre=(P*pre+ord(s1[i]))%Q seen.add(pre) for i in range(mid,n1): pre=(P*pre+ord(s1[i])-ord(s1[i-mid])*K)%Q seen.add(pre) pre=0 for i in range(mid): pre=(P*p...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务