思路

二分 + 字符串哈希

对于每次翻转，二分lcp即可，check函数通过字符串哈希进行哈希值快速获取，然后判断即可。

代码

# 字符串哈希
base, mod = 1331, 10**9 + 7
base_inv = pow(base,mod-2,mod)
def getPreHash(s):
    n = len(s)
    # hash前缀和
    pre_hash = [0] * (n+1)
    # 指数数组
    # pow_arr[i] 代表 mul 的 i 次方
    pow_arr = [0] * (n+1)
    pow_arr_inv = [0] * (n+1)
    # 可以使用两个mod组成二元组编码，防止hash碰撞
    # 或者mod足够大。。              
    tmp = 0
    mul = 1  
    mul_inv = 1
    # 次方从大到小
    for i in range(n):
        tmp = (tmp * base + ord(s[i])) % mod
        pre_hash[i+1] = tmp
        pow_arr[i] = mul 
        pow_arr_inv[i] = mul_inv
        mul = mul * base % mod
        mul_inv = mul_inv * base_inv % mod

    pow_arr[n] = mul
    pow_arr_inv[n] = mul_inv

    return pre_hash,pow_arr,pow_arr_inv     
# 获取[l,r)的hashcode值，长度为r-l
def getHash(pre_hash,pow_arr,l,r):
    return ((pre_hash[r] - pre_hash[l] * pow_arr[r-l])%mod + mod)%mod

    
for _ in range(int(input().strip())):
    n = int(input())
    s = input().strip()
    t = input().strip()
    pre_hash_s,_,_ = getPreHash(s)
    pre_hash_t,pow_arr,pow_arr_inv = getPreHash(t)
    
    maxt = 0
    pos = 1
    # 前i个字符反转
    # 反向滚动哈希，小到大
    tmp = 0
    mul = 1
    pre_hash = [0]
    for i in range(n):
        tmp += ord(s[i]) * mul
        tmp %= mod
        mul *= base
        mul %= mod
        pre_hash.append(tmp)
        # 二分
        start = 1
        end = n
        while start <= end:
            l = (start + end) // 2
            # 在翻转长度内
            if l <= i + 1:
                # 逆元
                p = (tmp - pre_hash[i+1-l]) * pow_arr_inv[i+1-l]
            # 超过翻转长度
            else:
                p = tmp * pow_arr[l-i-1] + getHash(pre_hash_s,pow_arr,i+1,l)
            p %= mod
                
            if p == getHash(pre_hash_t,pow_arr,0,l):
                start = l + 1
            else:
                end = l - 1
        start -= 1
        if maxt < start:
            maxt = start
            pos = i + 1
            
    print(maxt,pos)