问题理解

我们有一个长的点列（轨迹）$p_1, p_2, \dots, p_n$，和 $m$ 个短的点列（轨迹片段）$q^{(1)}, q^{(2)}, \dots, q^{(m)}$。
判断 $q$ 在 $p$ 的某个连续子列中出现，允许对 $q$ 进行任意次的：

• 平移
• 旋转
• 翻转（反射）
• 缩放（比例 ≠ 0）

即判断 $q$ 与 $p$ 的某个子列是否相似。

---

关键难点

1. 变换多样性：四种变换组合起来就是二维相似变换，有 4 个自由度（平移 2、旋转 1、缩放 1，翻转可视为旋转+反射）
2. 数据规模：$n, k$ 可达 $2\times 10^5$，片段总长度 $2\times 10^4$，需要高效算法

---

核心思路：提取不变量

相似变换下，有些几何量会改变（坐标、绝对长度），有些则保持不变。

相似不变量

• 相邻线段长度比
• 相邻线段之间的夹角
• 点的相对位置关系（共线、平行等）

但为了字符串匹配，我们需要一个序列表示。

---

标准化表示方法

步骤 1：转化为相对向量

对于点列 $a_1, a_2, \dots, a_k$，定义向量序列： [ \vec{v}i = a{i+1} - a_i \quad (i=1,\dots,k-1) ]

步骤 2：提取相似不变量

对每个向量 $\vec{v}_i = (x_i, y_i)$，计算：

• 长度 $L_i = \sqrt{x_i^2 + y_i^2}$
• 方向（与前一向量的夹角）

但长度受缩放影响，方向受旋转影响。

步骤 3：使用长度比和夹角

定义：

• 长度比：$r_i = \frac{L_{i+1}}{L_i}$（缩放不变）
• 转向角：$\theta_i = \text{angle}(\vec{v}_i, \vec{v}_{i+1})$（旋转、平移、缩放不变）
• 叉积符号：$\text{sign}(\vec{v}_i \times \vec{v}_{i+1})$（区分翻转）

实际上，常用的标准化方法是：

---

经典方法：点列标准化

1. 平移归一化

将点列平移到第一个点为原点： [ a'_i = a_i - a_1 ]

2. 旋转、翻转归一化

将第二个点 $a'_2$ 旋转到 x 轴正半轴：

• 计算 $a'_2$ 与 x 轴的夹角 $\alpha$
• 如果 $a'_2$ 在 x 轴负半轴方向，先翻转（y → -y）再旋转
• 对整个点列应用相同的旋转（和可能的翻转）

3. 缩放归一化

将点列缩放，使得 $|a'_2| = 1$

这样处理后：任意两个相似的点列会得到完全相同的标准化坐标（最多因翻转对称有两个版本）。

---

匹配算法

预处理主轨迹

对主轨迹 $p$ 的每个长度为 $k$ 的连续子列 $[i, i+k-1]$：

1. 标准化该子列
2. 将标准化后的坐标序列编码为一个"指纹"（哈希值）
3. 存入哈希表，记录出现位置

查询每个片段

对每个片段 $q$：

1. 标准化 $q$（考虑翻转的两个版本）
2. 计算指纹，在哈希表中查询出现次数

---

复杂度分析

• 主轨迹子列数：$O(nk)$ 太大，不能显式枚举
• 优化：使用滑动窗口计算标准化表示
  • 相邻窗口的标准化可以增量计算
  • 复杂度：$O(n \times \text{标准化成本})$

高效实现技巧

1. 向量化标准化：用复数表示点，旋转=乘法，标准化快速计算
2. 哈希滚动：像 Rabin-Karp 一样滚动计算子列哈希
3. 只处理必要长度：片段长度各不相同，只需处理实际存在的 $k$ 值

---

样例分析

样例：

主轨迹: (0,0), (1,0), (1,1)
片段1: (17,0), (10,1) → 长度2
片段2: (0,0), (1,0), (1,-1) → 长度3

片段1标准化：

• 平移：$(0,0), (-7,1)$
• 旋转到 x 轴：$(-7,1)$ 长度 $\sqrt{50}$，缩放后得到固定表示
• 在主轨迹中搜索长度为 2 的标准化子列

结果：片段1出现2次，片段2出现1次

---

边界情况处理

1. 共线点：标准化时第二个点为零向量？不可能，因输入保证相邻点不同
2. 缩放因子为 0：不允许，因缩放比例 p ≠ 0
3. 翻转对称：每个片段要检查原方向和翻转后方向
4. 浮点精度：用整数运算或误差容忍比较

---

总结

这道题的核心是：

1. 几何变换理解：相似变换的自由度与不变量
2. 标准化技术：通过平移、旋转、翻转、缩放将任意相似形状映射到标准形
3. 字符串匹配思想：将几何匹配转化为精确匹配
4. 算法优化：滑动窗口、哈希滚动处理大规模数据

通过标准化+哈希的方法，可以在 $O(n + M)$ 的近似复杂度解决（$M$=片段总长度），适用于大数据规模。