题解 | #公共子串计算#

看了下题解里好像没太有人用这个，二分法+滚动哈希

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