题目描述

小蓝有一个序列 a，同时他的朋友小乔有一个序列 b。

我们认为两个序列是和谐的，当且仅当存在某个数 x，使得对于所有的 i 有 ai​+x=bi​。

现在小蓝可以让序列 a 旋转，即通过一次参数为 k 的旋转可以将序列 a1​,a2​,⋯,an​ 变为 a1+k​,a2+k​,⋯,an​,a1​,a2​,⋯,ak​。

小蓝希望知道，是否存在这样的旋转操作，能够让序列 a 和 b 是和谐的。

输出共一行，一个自然数 k 表示参数为 k 的旋转操作能够让 a,b 是和谐的，如果存在多个这样的 k，请输出最小的 k，如果不存在这样的 k，请输出 −1。

输入格式

输入的第一行包含一个正整数 n。

第二行包含 n 个正整数 a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

第三行包含 n 个正整数 b1​,b2​,⋯,bn​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，如果不存在，请输出整数 −1。

输入输出样例

输入

4
2 3 4 5
2 3 4 1

输出

1

说明/提示

【样例说明】

小蓝可以让序列 a 旋转得到 3 4 5 2，根据和谐序列的定义，令 x=−1，那么此时 a,b 就是和谐的。

【评测用例规模与约定】

对于 50% 的评测用例，n≤3000；

对于 80% 的评测用例，对于任意 i不等于j 有 ai​不等于aj​；

对于所有评测用例，1≤n≤5×105，1≤ai​,bi​≤109。

--------------------------------------------------------------------------------------------

本文借鉴了 洛谷的@imnotcfz P12877 [蓝桥杯 2025 国 Python A] 心意 题解 - 洛谷专栏

--------------------------------------------------------------------------------------------

首先题目要求对a进行旋转 序列 a 旋转，即通过一次参数为 k 的旋转可以将序列a1​,a2​,⋯,an​ 变为 a1+k​,a2+k​,⋯,an​,a1​,a2​,⋯,ak​

言外之意就是把序列a进行倍增

可以通过枚举法 对参数k进行一次次的匹配 由此可以得出我们的第一个尝试

第一次尝试：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 检查每个可能的旋转参数k
for k in range(n):
    # 计算x值（根据旋转后第一个元素的关系）
    x = b[0] - a[k]
    
    # 检查所有元素是否满足和谐条件
    is_harmonic = True
    for i in range(1, n):
        # 旋转后a的第i个元素是a[(k+i) % n]
        if a[(k+i) % n] + x != b[i]:
            is_harmonic = False
            break
    
    if is_harmonic:
        print(k)
        exit()

# 如果没有找到合适的k
print(-1)

但是提交后发现 后面全都是tle 超时了

首先我们的方法肯定没有错误 于是乎肯定是范围或者算法复杂度的问题 回头看

我们的程序时间复杂度为 O(n2)，即使是效率更高的 C++ 也只有 60pts 

那么很明了 要把时间复杂度下降  但是如何下降是个问题 

看我们的方法 是由b序列中的元素一个一个匹配过去 

关于匹配算法 于是想到了我们的KMP算法

但显然不能直接这么搞，因为题目要求 a 数组加上一个数 x 后才能得到 b 数组

因此我们需要一些转化

------

实际上能否匹配成功与 a、b 的具体取值无关，而在于元素之间的变化量是否一致。说到变化量，我们可以使用环形差分求出变化量，这样就可以直接通过 KMP 算法找出答案

------

第二次修改：

以上为关键点 但是什么叫环形序列？什么叫差分？

• 环形序列：指首尾相连的序列（类似圆环）。例如数组 [a1, a2, a3] 作为环形序列时，a3 的下一个元素是 a1，a1 的前一个元素是 a3。
• 差分（变化量）：对于线性序列（非环形），“变化量” 通常指相邻元素的差值。例如序列 [x1, x2, x3] 的差分是 [x2-x1, x3-x2]，反映相邻元素的 “变化幅度”。

环形差分的定义：

“环形差分” 是针对环形序列的差分计算，核心是必须包含首尾元素的差值（因为环形序列首尾相连），从而完整反映整个环形的 “变化量循环”。

具体来说：
对于环形序列 S = [s1, s2, ..., sn]，其环形差分序列 D 定义为：
D = [s2-s1, s3-s2, ..., sn-s(n-1), s1 - sn]

可以看到，环形差分序列有 n 个元素（与原序列长度相同），最后一个元素是 “首元素减尾元素”，体现了 “环形闭合” 的特性。

环形差分的作用：捕捉 “变化量模式”

环形差分的核心价值是剥离元素具体取值，只保留相邻元素的变化关系。

例如：

• 环形序列 A = [1, 3, 6] 的环形差分是 [3-1=2, 6-3=3, 1-6=-5]，即 D_A = [2, 3, -5]。
• 环形序列 B = [3, 6, 1]（A 旋转后的结果）的环形差分是 [6-3=3, 1-6=-5, 3-1=2]，即 D_B = [3, -5, 2]。

可以发现：D_B 是 D_A 的 “旋转版本”（元素顺序循环移位）。这意味着：两个环形序列若旋转后完全相同，它们的环形差分序列也必然是旋转等价的。

总结

“环形差分求出变化量” 是指：对环形序列计算包含首尾元素差值的相邻元素差分，得到的环形差分序列可精准反映元素间的变化关系。这种变化关系在序列旋转时保持 “旋转等价”，因此可通过 KMP 等字符串匹配算法快速判断两个环形序列是否匹配（即变化量模式一致）。

KMP算法的示例和应用：

KMP 算法是一个经典的字符串匹配算法。字符串匹配是一个非常基本的操作，也就是在一个字符串中寻找另一个子串。它通过预处理模式串构建部分匹配表（也称为最长前缀后缀数组），从而在匹配过程中避免不必要的字符比较，提高匹配效率。

def compute_lps(pattern):
    """计算最长前缀后缀数组（部分匹配表）"""
    m = len(pattern)
    lps = [0] * m  # 初始化最长前缀后缀数组
    length = 0  # 记录当前最长前缀后缀的长度
    
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # 回溯到上一个可能的匹配位置
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    """使用KMP算法在文本中查找模式串，返回所有匹配的起始索引"""
    n = len(text)
    m = len(pattern)
    if m == 0:
        return []
    
    lps = compute_lps(pattern)
    i = 0  # 文本的索引
    j = 0  # 模式串的索引
    matches = []  # 存储所有匹配的起始索引
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            # 找到一个匹配，记录起始位置
            matches.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                # 根据部分匹配表回溯
                j = lps[j - 1]
            else:
                i += 1
    return matches

# 使用案例
if __name__ == "__main__":
    # 示例1：简单文本匹配
    text1 = "ABABDABACDABABCABAB"
    pattern1 = "ABABCABAB"
    print(f"文本: {text1}")
    print(f"模式串: {pattern1}")
    print(f"匹配位置: {kmp_search(text1, pattern1)}")  # 输出: [10]
    
    # 示例2：多个匹配
    text2 = "ABC ABCDAB ABCDABCDABDE"
    pattern2 = "ABCDABD"
    print(f"\n文本: {text2}")
    print(f"模式串: {pattern2}")
    print(f"匹配位置: {kmp_search(text2, pattern2)}")  # 输出: [15]
    
    # 示例3：DNA序列匹配
    dna_sequence = "ATCGATCGATCGATCGATCG"
    target_sequence = "ATCG"
    print(f"\nDNA序列: {dna_sequence}")
    print(f"目标序列: {target_sequence}")
    print(f"匹配位置: {kmp_search(dna_sequence, target_sequence)}")  # 输出: [0, 4, 8, 12, 16]

KMP代码解析

这个 KMP 算法实现包含两个主要函数：

1. compute_lps(pattern)：计算模式串的最长前缀后缀数组（LPS 数组）

   • LPS 数组的每个元素表示模式串中对应位置前的子串的最长前缀后缀长度
   • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
   • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

2. kmp_search(text, pattern)：使用 KMP 算法进行字符串匹配

   • 利用 LPS 数组在匹配失败时进行高效回溯，避免重新比较已经匹配过的字符
   • 返回模式串在文本中所有出现的起始索引

题目实际代码示例（引用）：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 计算差分数组
differenceA, differenceB = [], []
# 特判第一个数字
differenceA.append(a[0] - a[n - 1])
differenceB.append(b[0] - b[n - 1])
for i in range(1, n):
    differenceA.append(a[i] - a[i - 1])
    differenceB.append(b[i] - b[i - 1])
# 破环成链
differenceA += differenceA
# 为了方便查找，将差分数组转换为字符串
stringA = ','.join(map(str, differenceA))
stringB = ','.join(map(str, differenceB))
# 核心算法：字符串匹配
result = stringA.find(stringB)
if result == -1:  # 若不存在则输出 -1
    print(result)
else:
    # 接下来我们需要找到下标 result 对应的是第几个数字
    currentPosition = 0  # 表示字符串中的位置
    for index, number in enumerate(differenceA):
        if currentPosition == result:
            print(index)
            break
        currentPosition += len(str(number)) + 1

这里用到了KMP算法中的str类的find方法 通过调用内置的help(str.find)可以得到相关信息

find(self, sub[, start[, end]], /) builtins.str 方法
    返回 S 中找到子串 sub 的最小索引，使得 sub 包含在 S[start:end] 之间。

    可选形参 start 和 end 与切片表示法一致。
    失败时返回 -1。

该题需要熟练掌握KMP算法匹配的应用 通过变化量抽象到具体数值匹配 想象力需要大于实际能力