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

二分搜索+滚动哈希

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

P,Q=131,2**64
s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dic={}
if n2>n1:
    s1,s2,n1,n2=s2,s1,n2,n1
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*pre+ord(s2[i]))%Q
    if pre in seen:
        dic[mid]=i-mid+1
        return True
    for i in range(mid,n2):
        pre=(P*pre+ord(s2[i])-ord(s2[i-mid])*K)%Q
        if pre in seen:
            dic[mid]=i-mid+1
            return True
    return False        
l,r=0,min(n1,n2)
longest=0
while l<r:
    mid=1+(l+r)//2
    if hsm(mid):
        l=mid
        longest=mid
    else:
        r=mid-1
a=dic[longest]
print(s2[a:a+longest])